Article in volume
Authors:
Behnaz Pahlavsay
Department of Mathematics,
Hokkaido University,
Kita 10, Nishi 8, Kita-Ku,
Sapporo 060-0810, Japan.
Elisa Palezzato
Department of Mathematics,
Hokkaido University,
Kita 10, Nishi 8, Kita-Ku,
Sapporo 060-0810, Japan.
Michele Torielli
Department of Mathematics,
GI-CoRE GSB,
Hokkaido University,
Kita 10, Nishi 8, Kita-Ku,
Sapporo 060-0810, Japan.
Title:
3-tuple total domination number of rook's graphs
PDFSource:
Discussiones Mathematicae Graph Theory 42(1) (2022) 15-37
Received: 2018-09-11 , Revised: 2019-03-11 , Accepted: 2019-06-13 , Available online: 2019-10-04 , https://doi.org/10.7151/dmgt.2242
Abstract:
A $k$-tuple total dominating set ($k$TDS) of a graph $G$ is a set $S$ of
vertices in which every vertex in $G$ is adjacent to at least $k$ vertices
in $S$. The minimum size of a $k$TDS is called the $k$-tuple total dominating
number and it is denoted by $\gamma_{× k,t}(G)$. We give a constructive
proof of a general formula for $\gamma_{× 3, t} (K_n \Box K_m)$.
Keywords:
$k$-tuple total domination, Cartesian product of graphs, rook's graph, Vizing's conjecture
References:
- J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008).
- B. Brešar, P. Dorbec, W. Goddard, B. Hartnell, M. Henning, S. Klavžar and D. Rall, Vizing's conjecture: a survey and recent results, J. Graph Theory 69 (2012) 46–76.
https://doi.org/10.1002/jgt.20565 - B. Brešar, M.A. Henning and S. Klavžar, On integer domination in graphs and Vizing-like problems, Taiwanese J. Math. 10 (2006) 1317–1328.
https://doi.org/10.11650/twjm/1500557305 - B. Brešar, M.A. Henning and D.F. Rall, Paired-domination of Cartesian products of graphs, Util. Math. 73 (2007) 255–265.
- P.A. Burchett, On the border queens problem and $k$-tuple domination on the rook's graph, Congr. Numer. 209 (2011) 179–187.
- P.A. Burchett, D. Lane and J.A. Lachniet, k-tuple and k-domination on the rook's graph and other results, Congr. Numer. 199 (2009) 187–204.
- K. Choudhary, S. Margulies and I.V. Hicks, A note on total and paired domination of Cartesian product graphs, Electron. J. Combin. 20(3) (2013) #P25.
https://doi.org/10.37236/2535 - K. Choudhary, S. Margulies and I.V. Hicks, Integer domination of Cartesian product graphs, Discrete Math. 338 (2015) 1239–1242.
https://doi.org/10.1016/j.disc.2015.01.032 - E.W. Clark and S. Suen, An inequality related to Vizing's Conjecture, Electron. J. Combin. 7 (2000) #N4.
https://doi.org/10.37236/1542 - D.C. Fisher, J. Ryan, G. Domke and A. Majumdar, Fractional domination of strong direct products, Discrete Appl. Math. 50 (1994) 89–91.
https://doi.org/10.1016/0166-218X(94)90165-1 - F. Harary and T.W. Haynes, Double domination in graphs, Ars Combin. 55 (2000) 201–213.
- T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).
- T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998).
- M.A. Henning and A.P. Kazemi, k-tuple total domination in cross products of graphs, J. Comb. Optim. 24 (2012) 339–346.
https://doi.org/10.1007/s10878-011-9389-z - M.A. Henning and A.P. Kazemi, k-tuple total domination in graphs, Discrete Appl. Math. 158 (2010) 1006–1011.
https://doi.org/10.1016/j.dam.2010.01.009 - M.A. Henning and D.F. Rall, On the total domination number of Cartesian products of graphs, Graphs Combin. 21 (2005) 63–69.
https://doi.org/10.1007/s00373-004-0586-8 - P.T. Ho, A note on the total domination number, Util. Math. 77 (2008) 97–100.
- X.M. Hou and F. Jiang, Paired domination of Cartesian products of graphs, J. Math. Res. Exposition 30 (2010) 181–185.
- X.M. Hou and Y. Lu, On the $\{k\}$-domination number of Cartesian products of graphs, Discrete Math. 309 (2009) 3413–3419.
https://doi.org/10.1016/j.disc.2008.07.030 - W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (John Wiley & Sons, New York, 2000).
- A.P. Kazemi and B. Pahlavsay, k-tuple total domination in supergeneralized Petersen graphs, Comm. Math. Appl. 2 (2011) 21–30.
- A.P. Kazemi, B. Pahlavsay and R.J. Stones, Cartesian product graphs and k-tuple total domination, Filomat 32 (2018) 6713–6731.
https://doi.org/10.2298/FIL1819713K - V.G. Vizing, Some unsolved problems in graph theory, Russ. Math. Surveys 23 (1968) 125–145.
https://doi.org/10.1070/RM1968v023n06ABEH001252
Close