Vizing’s conjecture for graphs with domination number 3 – a new proof. (English) Zbl 1323.05099

Brešar, Boštjan

Electron. J. Comb. 22, No. 3, Research Paper P3.38, 8 p. (2015).

Summary: Vizing’s conjecture [V. G. Vizing, Russ. Math. Surv. 23, No. 6, 125–141 (1968); translation from Usp. Mat. Nauk 23, No. 6(144), 117–134 (1968; Zbl 0192.60502)] asserts that the domination number of the Cartesian product of two graphs is at least as large as the product of their domination numbers. In this note we use a new, transparent approach to prove Vizing’s conjecture for graphs with domination number 3; that is, we prove that for any graph \(G\) with \(\gamma(G)=3\) and an arbitrary graph \(H\), \(\gamma(G\square H) \geq 3\gamma(H)\).

MSC:

05C69	Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C76	Graph operations (line graphs, products, etc.)

Keywords:

Cartesian product; domination; Vizing’s conjecture