×

zbMATH — the first resource for mathematics

Vizing’s conjecture: A two-thirds bound for claw-free graphs. (English) Zbl 1368.05113
Summary: We show that for any claw-free graph \(G\) and any graph \(H\), \(\gamma(G \square H) \geq \frac{2}{3} \gamma(G) \gamma(H)\), where \(\gamma(G)\) is the domination number of \(G\).

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 arXiv
References:
[1] Allan, R. B.; Laskar, R., On domination and independent domination numbers of a graph, Discrete Math., 23, 73-76, (1978) · Zbl 0416.05064
[2] Bartsalkin, A. M.; German, L. F., The external stability number of the Cartesian product of graphs, Bul. Akad. Stiinte RSS Moldoven, 5-8, 1, 94, (1979) · Zbl 0457.05053
[3] Brešar, B., Vizing’s conjecture for graphs with domination number 3 - a new proof, Electron. J. Combin., 22, 3, P3.38, (2015) · Zbl 1323.05099
[4] Brešar, B.; Dorbec, P.; Goddard, W.; Hartnell, B.; Henning, M.; Klavžar, S.; Rall, D., Vizing’s conjecture: a survey and recent results, J. Graph Theory, 69, 1, 46-76, (2012) · Zbl 1234.05173
[5] Contractor, A.; Krop, E., A class of graphs approaching vizing’s conjecture, Theory and Applications of Graphs, 3, 1, (2016), Article 4 · Zbl 1416.05208
[6] Diestel, R., (Graph Theory, Graduate Texts in Mathematics, vol. 173, (2005), Springer-Verlag, Heidelberg, New York) · Zbl 1074.05001
[7] Suen, S.; Tarr, J., An improved inequality related to vizing’s conjecture, Electron. J. Combin., 19, 1, P8, (2012) · Zbl 1243.05190
[8] Sun, L., A result on vizing’s conjecture, Discrete Math., 275, 1-3, 363-366, (2004) · Zbl 1030.05087
[9] Vizing, V. G., The Cartesian product of graphs, Vycisl. Sistemy, 9, 30-43, (1963) · Zbl 0931.05033
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.