Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Vizing's conjecture and the one-half argument

100%

Hartnell B., Rall D.

Discussiones Mathematicae Graph Theory

1995

tom 15

nr 2

205-216

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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Hartnell B.

1 Rall D.

1 1995

Wyniki wyszukiwania

Vizing's conjecture and the one-half argument