×

Some results on domination number of products of graphs. (English) Zbl 0904.05048

A dominating set in a graph \(G\) is a subset \(D\) of the vertex set of \(G\) with the property that each vertex of \(G\) either is in \(D\), or is adjacent to a vertex of \(D\). The minimum number of vertices of a dominating set in \(G\) is the domination number \(\gamma (G)\) of \(G\). The minimum number of vertices of a dominating set in \(G\) which induces a connected subgraph of \(G\) is the connected domination number \(\gamma_c(G)\) of \(G\). A conjecture of V. G. Vizing says that for the Cartesian product \(G\times H\) of graphs \(G\) and \(H\) the inequality \(\gamma (G\times H) \geq\gamma (G)\cdot \gamma (H)\) holds. The main theorem of the paper states that this inequality holds in the case when \(\gamma (H)\neq \gamma_c (H)\). In particular, it holds if \(H\) is a path or a circuit. Further a lower bound and an upper bound for the domination number of the Cartesian product of two paths are found, both in terms of their lengths.

MSC:

05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Cockayne, E. J., Hare, E. O., Hedetniemi, S. T. and Wimer, T. V., Bounds for the domination number of grid graph, Congr. Numer., 47(1985),217–228.
[2] El-Zahar, M., Parck, C. M.. Domination number of products of graphs, Ars Combin.,31 (1991), 223–227. · Zbl 0746.05067
[3] Jacobson, M. S., Kinch, L. F., On the domination number of products of graphs I, Ars Combin., 18(1983),33–44. · Zbl 0566.05050
[4] Jacobson, M. S., Kinch, L. F., On the domination of the products of graphs II, Tree, Journal of GraphTheory, 10(1986),97–106. · Zbl 0584.05053
[5] Vizing, V. G., A bound on the external stability number of a graph, Doklady A. N., 164(1965), 729–731. · Zbl 0136.44703
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.