×

Dominating Cartesian products of cycles. (English) Zbl 0824.05037

A set of vertices \(D\) in a graph is dominating if every vertex of the graph is adjacent to some vertex from \(D\). The domination number of the graph is the size of a smallest dominating set. The paper discusses the computation of the domination number of Cartesian products of graphs and an algorithm for finding minimum dominating sets in such graphs.

MSC:

05C35 Extremal problems in graph theory
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI

Online Encyclopedia of Integer Sequences:

Domination number of the Cartesian product of two n-cycles.

References:

[1] Biggs, N., Algebraic Graph Theory (1974), Cambridge University Press: Cambridge University Press London · Zbl 0284.05101
[2] Chang, T.; Clark, E., The domination numbers of the 5 × \(n\) and 6 × \(n\) grid graphs, J. Graph Theory, 17, 81-107 (1993) · Zbl 0780.05030
[3] Clark, B. N.; Colbourn, C. J.; Johnson, D. S., Unit disc graphs, Discrete Math., 86, 165-177 (1990) · Zbl 0739.05079
[4] El-Zahar, M.; Pareek, C. M., Domination number of products of graphs, Ars Combin., 31, 223-227 (1991) · Zbl 0746.05067
[5] Faudree, R. J.; Schelp, R. H., The domination number for the product of graphs, (Congr. Numer., 79 (1990)), 29-33 · Zbl 0862.05060
[6] Hartnell, B. L.; Rall, D. F., On Vizing’s conjecture, (Congr. Numer., 82 (1991)), 87-96 · Zbl 0764.05092
[7] Hedetniemi, S. T.; Laskar, R. C., Introduction, Discrete Math., 86, 3-9 (1990) · Zbl 0728.05056
[8] Jacobson, M. S.; Kinch, L. F., On the domination number of products of graphs I, Ars Combin., 18, 33-44 (1983) · Zbl 0566.05050
[9] Jacobson, M. S.; Kinch, L. F., On the domination of the products of graphs II: trees, J. Graph Theory, 10, 97-106 (1986) · Zbl 0584.05053
[10] Vizing, V. G., The Cartesian product of graphs, Vychisl. 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. 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.