zbMATH — the first resource for mathematics

\(k\)-tuple total domination in cross products of graphs. (English) Zbl 1261.90073
Summary: For \(k\geq 1\) an integer, a set \(S\) of vertices in a graph \(G\) with minimum degree at least \(k\) is a \(k\)-tuple total dominating set of \(G\) if every vertex of \(G\) is adjacent to at least \(k\) vertices in \(S\). The minimum cardinality of a \(k\)-tuple total dominating set of \(G\) is the \(k\)-tuple total domination number of \(G\). When \(k=1\), the \(k\)-tuple total domination number is the well-studied total domination number. In this paper, we establish upper and lower bounds on the \(k\)-tuple total domination number of the cross product graph \(G\times H\) for any two graphs \(G\) and \(H\) with minimum degree at least \(k\). In particular, we determine the exact value of the \(k\)-tuple total domination number of the cross product of two complete graphs.

90C35 Programming involving graphs or networks
Full Text: DOI
[1] El-Zahar M, Gravier S, Klobucar A (2008) On the total domination number of cross products of graphs. Discrete Math 308:2025–2029 · Zbl 1168.05344
[2] Burger AP, Henning MA, van Vuuren JH (2009) On the ratios between packing and domination parameters of a graph. Discrete Math 309:2473–2478 · Zbl 1211.05103
[3] Harary F, Haynes TW (2000) Double domination in graphs. Ars Comb 55:201–213 · Zbl 0993.05104
[4] Haynes TW, Hedetniemi ST, Slater PJ (eds) (1998a) Fundamentals of domination in graphs. Marcel Dekker, New York
[5] Haynes TW, Hedetniemi ST, Slater PJ (eds) (1998b) Domination in graphs: advanced topics. Marcel Dekker, New York
[6] Henning MA, Kazemi AP (2010) k-Tuple total domination in graphs. Discrete Appl Math 158:1006–1011 · Zbl 1210.05097
[7] Liao CS, Chang GJ (2002) Algorithmic aspects of k-tuple domination in graphs. Taiwan J Math 6:415–420 · Zbl 1047.05032
[8] Liao CS, Chang GJ (2003) k-Tuple domination in graphs. Inf Process Lett 87:45–50 · Zbl 1175.68299
[9] Nowakowski RJ, Rall DF (1996) Associative graph products and their independence, domination and coloring numbers. Discuss Math, Graph Theory 16:53–79 · Zbl 0865.05071
[10] Rall DF (2005) Total domination in categorical products of graphs. Discuss Math, Graph Theory 25:35–44 · Zbl 1074.05068
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.