- Tytuł:
- Vizings conjecture and the one-half argument
- Autorzy:
-
Hartnell, Bert
Rall, Douglas - Powiązania:
- https://bibliotekanauki.pl/articles/972044.pdf
- Data publikacji:
- 1995
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
domination number
Cartesian product
Vizing's conjecture
clique - Opis:
- The domination number of a graph G is the smallest order, γ(G), of a dominating set for G. A conjecture of V. G. Vizing [5] states that for every pair of graphs G and H, γ(G☐H) ≥ γ(G)γ(H), where G☐H denotes the Cartesian product of G and H. We show that if the vertex set of G can be partitioned in a certain way then the above inequality holds for every graph H. The class of graphs G which have this type of partitioning includes those whose 2-packing number is no smaller than γ(G)-1 as well as the collection of graphs considered by Barcalkin and German in [1]. A crucial part of the proof depends on the well-known fact that the domination number of any connected graph of order at least two is no more than half its order.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 1995, 15, 2; 205-216
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł