×

zbMATH — the first resource for mathematics

Improving the Clark-Suen bound on the domination number of the Cartesian product of graphs. (English) Zbl 1367.05155
Summary: A long-standing Vizing’s conjecture asserts that the domination number of the Cartesian product of two graphs is at least as large as the product of their domination numbers; one of the most significant results related to the conjecture is the bound of W. E. Clark and S. Suen [Electron. J. Comb. 7, No. 1, Notes N4, 3 p. (2000; Zbl 0947.05056)], \(\gamma(G \square H) \geq \gamma(G) \gamma(H)/2\), where \(\gamma\) stands for the domination number, and \(G \square H\) is the Cartesian product of graphs \(G\) and \(H\). In this note, we improve this bound by employing the 2-packing number \(\rho(G)\) of a graph \(G\) into the formula, asserting that \(\gamma(G \square H) \geq(2 \gamma(G) - \rho(G)) \gamma(H)/3\). The resulting bound is better than that of Clark and Suen whenever \(G\) is a graph with \(\rho(G) < \gamma(G)/2\), and in the case \(G\) has diameter 2 reads as \(\gamma(G \square H) \geq(2 \gamma(G) - 1) \gamma(H)/3\).

MSC:
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C76 Graph operations (line graphs, products, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aharoni, Ron; Szabó, Tibor, Vizing’s conjecture for chordal graphs, Discrete Math., 309, 6, 1766-1768, (2009) · Zbl 1211.05098
[2] Brešar, Boštjan; Dorbec, Paul; Goddard, Wayne; Hartnell, Bert L.; Henning, Michael A.; Klavžar, Sandi; Rall, Douglas F., Vizing’s conjecture: a survey and recent results, J. Graph Theory, 69, 1, 46-76, (2012) · Zbl 1234.05173
[3] Clark, W. Edwin; Suen, Stephen, An inequality related to vizing’s conjecture, Electron. J. Combin., 7, 3, (2000), Note 4 (electronic) · Zbl 0947.05056
[4] Hartnell, Bert L.; Rall, Douglas F., Domination in Cartesian products: vizing’s conjecture, (Domination in Graphs, Monogr. Textbooks Pure Appl. Math., 209, (1998), Dekker New York), 163-189 · Zbl 0890.05035
[5] Domination in graphs, (Haynes, Teresa W.; Hedetniemi, Stephen T.; Slater, Peter J., Monographs and Textbooks in Pure and Applied Mathematics, 209, (1998), Marcel Dekker, Inc. New York), xiv+497, Advanced topics · Zbl 0890.05002
[6] Haynes, Teresa W.; Hedetniemi, Stephen T.; Slater, Peter J., Fundamentals of domination in graphs, (Monographs and Textbooks in Pure and Applied Mathematics, 208, (1998), Marcel Dekker, Inc. New York), xii+446 · Zbl 0890.05002
[7] Suen, Stephen; Tarr, Jennifer, An improved inequality related to vizing’s conjecture, Electron. J. Combin., 19, 1, (2012), Paper 8, 4 · Zbl 1243.05190
[8] Vizing, Vadim G., The Cartesian product of graphs, VyČisl. Sistemy No., 9, 30-43, (1963)
[9] Vizing, Vadim G., Some unsolved problems in graph theory, Uspekhi Mat. Nauk, 23, 6(144), 117-134, (1968)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.