×

zbMATH — the first resource for mathematics

Domination in Cartesian products: Vizing’s conjecture. (English) Zbl 0890.05035
Haynes, Teresa W. (ed.) et al., Domination in graphs. Advanced topics. New York, NY: Marcel Dekker. Pure Appl. Math., Marcel Dekker. 209, 163-189 (1998).
The Cartesian product of two graphs \(G\) and \(H\) with vertex sets \(V(G)\) and \(V(H)\), and edge sets \(E(G)\) and \(E(H)\), respectively, is defined in the following way. The vertex set consists of the normal Cartesian product of \(V(G)\) and \(V(H)\). Then, vertices \((x_1,y_1)\) and \((x_2, y_2)\) in \(V(G)\times V(H)\) are adjacent if \(x_1= x_2\) and \(y_1y_2\in E(H)\), or \(y_1= y_2\) and \(x_1x_2\in E(G)\). The domination number of a graph \(G\) is the cardinality of the smallest set \(A\) such that every vertex of \(G\) is either in \(A\) or adjacent to an element of \(A\).
Vizing’s conjecture states that the domination number of the Cartesian product of \(G\) and \(H\), is at least as big as the product of the domination numbers of \(G\) and \(H\). This paper surveys the progress and methods of attack on this conjecture, and also mentions some other types of product. The survey is reasonably thorough, though the paper is sometimes unclear due to crucial definitions and notation being omitted.
For the entire collection see [Zbl 0883.00011].

MSC:
05C35 Extremal problems in graph theory
PDF BibTeX XML Cite