On domination numbers of graph bundles
Abstract
Let ▫$\gamma(G)$▫ be the domination number of a graph ▫$G$▫. It is shown that for any ▫$k \ge 0$▫ there exists a Cartesian graph bundle ▫$B \Box_\varphi F$▫ such that ▫$\gamma(B \Box_\varphi F) = \gamma(B)\gamma(F) - 2k$▫. The domination numbers of Cartesian bundles of two cycles are determined exactly when the fibre graph is a triangle or a square. A statement similar to Vizing's conjecture on strong graph bundles is shown not to be true by proving the inequality ▫$\gamma(B \boxtimes_\varphi F) \le \gamma(B)\gamma(F)$▫ for strong graph bundles. Examples of graphs ▫$B$▫ and ▫$F$▫ with ▫$\gamma(B \boxtimes_\varphi F) < \gamma(B)\gamma(F)$▫ are given.
Keywords
matematika;teorija grafov;kartezični produkt grafov;dominantno število;dominantna množica;grafovski sveženj;mathematics;graph theory;graph bundle;dominating set;domination number;Cartesian product;
Data
| Language: | English |
|---|---|
| Year of publishing: | 2005 |
| Typology: | 0 - Not set |
| Organization: | UM FS - Faculty of Mechanical Engineering |
| UDC: | 519.17 |
| COBISS: |
13826905
|
| ISSN: | 1318-4865 |
| Views: | 1008 |
| Downloads: | 85 |
| Average score: | 0 (0 votes) |
| Metadata: |
|
Other data
| Secondary language: | Unknown |
|---|---|
| Secondary keywords: | matematika;teorija grafov;kartezični produkt grafov;dominantno število;dominantna množica;grafovski sveženj; |
| URN: | URN:SI:UM: |
| Type (COBISS): | Not categorized |
| Pages: | str. 1-10 |
| Volume: | ǂVol. ǂ43 |
| Issue: | ǂšt. ǂ998 |
| Chronology: | 2005 |
| ID: | 66705 |
Recommended works:
On domination numbers of graph bundles
2005,
no subtitle data available
Recognizing Cartesian products in linear time
2007,
no subtitle data available
Recognizing weighted directed Cartesian graph bundles
2000,
no subtitle data available
Vizing's conjecture: a survey and recent results
2009,
no subtitle data available
Wide diameter of Cartesian graph bundles
2010,
no subtitle data available