Geodesic
On Grundy Total Domination Number in Product Graphs
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 1, pp. 225-247.

Voir la notice de l'article provenant de la source Library of Science

A longest sequence (v_1, . . ., v_k) of vertices of a graph G is a Grundy total dominating sequence of G if for all i, N(υ_i)\⋃_j=1^i-1N(υ_j)≠∅. The length k of the sequence is called the Grundy total domination number of G and denoted γ_gr^t(G). In this paper, the Grundy total domination number is studied on four standard graph products. For the direct product we show that γ_gr^t(G×H)≥γ_gr^t(G)γ_gr^t(H), conjecture that the equality always holds, and prove the conjecture in several special cases. For the lexicographic product we express γ_gr^t(G∘H) in terms of related invariant of the factors and find some explicit formulas for it. For the strong product, lower bounds on γ_gr^t(G⊠H) are proved as well as upper bounds for products of paths and cycles. For the Cartesian product we prove lower and upper bounds on the Grundy total domination number when factors are paths or cycles.
Keywords: total domination, Grundy total domination number, graph product 
@article{DMGT_2021_41_1_a14,
     author = {Bre\v{s}ar, Bo\v{s}tjan and Bujt\'as, Csilla and Gologranc, Tanja and Klav\v{z}ar, Sandi and Ko\v{s}mrlj, Ga\v{s}per and Marc, Tilen and Patk\'os, Bal\'azs and Tuza, Zsolt and Vizer, M\'at\'e},
     title = {On {Grundy} {Total} {Domination} {Number} in {Product} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {225--247},
     publisher = {mathdoc},
     volume = {41},
     number = {1},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a14/}
}
TY  - JOUR
AU  - Brešar, Boštjan
AU  - Bujtás, Csilla
AU  - Gologranc, Tanja
AU  - Klavžar, Sandi
AU  - Košmrlj, Gašper
AU  - Marc, Tilen
AU  - Patkós, Balázs
AU  - Tuza, Zsolt
AU  - Vizer, Máté
TI  - On Grundy Total Domination Number in Product Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 225
EP  - 247
VL  - 41
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a14/
LA  - en
ID  - DMGT_2021_41_1_a14
ER  - 
%0 Journal Article
%A Brešar, Boštjan
%A Bujtás, Csilla
%A Gologranc, Tanja
%A Klavžar, Sandi
%A Košmrlj, Gašper
%A Marc, Tilen
%A Patkós, Balázs
%A Tuza, Zsolt
%A Vizer, Máté
%T On Grundy Total Domination Number in Product Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 225-247
%V 41
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a14/
%G en
%F DMGT_2021_41_1_a14
Brešar, Boštjan; Bujtás, Csilla; Gologranc, Tanja; Klavžar, Sandi; Košmrlj, Gašper; Marc, Tilen; Patkós, Balázs; Tuza, Zsolt; Vizer, Máté. On Grundy Total Domination Number in Product Graphs. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 1, pp. 225-247. http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a14/

[1] A. Aazami, Hardness results and approximation algorithms for some problems on graphs, Ph.D. Thesis (University of Waterloo, 2008). http://hdl.handle.net/10012/4147

[2] AIM Minimum Rank-Special Graphs Work Group, Zero-forcing sets and the minimum rank of graphs, Linear Algebra Appl. 428 (2008) 1628–1648. doi: 10.1016/j.laa.2007.10.009

[3] T. Ansill, B. Jacob, J. Penzellna and D. Saavedra, Failed skew zero forcing on a graph, Linear Algebra Appl. 509 (2016) 40–63. doi: 10.1016/j.laa.2016.07.019

[4] F. Barioli, W. Barrett, S.M. Fallat, H.T. Hall, L. Hogben, B. Shader, P. van den Driessche and H. van der Holst, Parameters related to tree-width, zero forcing, and maximum nullity of a graph, J. Graph Theory 72 (2013) 146–177. doi: 10.1002/jgt.21637

[5] K.F. Benson, D. Ferrero, M. Flagg, V. Furst, L. Hogben, V. Vasilevskak and B. Wissman, Power domination and zero forcing, Australas. J. Combin. 70 (2018) 221–235.

[6] B. Brešar, Cs. Bujtás, T. Gologranc, S. Klavžar, G. Košmrlj, B. Patkós, Zs. Tuza and M. Vizer, Dominating sequences in grid-like and toroidal graphs, Electron. J. Combin. 23 (2016) P4.34.

[7] B. Brešar, Cs. Bujtás, T. Gologranc, S. Klavžar, G. Košmrlj, B. Patkós, Zs. Tuza and M. Vizer, Grundy dominating sequences and zero forcing sets, Discrete Optim. 26 (2017) 66–77. doi: 10.1016/j.disopt.2017.07.001

[8] B. Brešar, P. Dorbec, W. Goddard, B. Hartnell, M.A. Henning, S. Klavžar and D.F. Rall, Vizing's conjecture: a survey and recent results, J. Graph Theory 69 (2012) 46–76. doi: 10.1002/jgt.20565

[9] B. Brešar, T. Kos, G. Nasini and P. Torres, Total dominating sequences in trees, split graphs, and under modular decomposition, Discrete Optim. 28 (2018) 16–30. doi: 10.1016/j.disopt.2017.10.002

[10] B. Brešar, T. Gologranc, M. Milanič, D.F. Rall and R. Rizzi, Dominating sequences in graphs, Discrete Math. 336 (2014) 22–36. doi: 10.1016/j.disc.2014.07.016

[11] B. Brešar, M.A. Henning and D.F. Rall, Total dominating sequences in graphs, Discrete Math. 339 (2016) 1665–1676. doi: 10.1016/j.disc.2016.01.017

[12] L.M. DeAlba, Some results on minimum skew zero forcing sets, and skew zero forcing number (2014). arXiv preprint, arXiv:1404.1618

[13] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, Second Edition (CRC Press, Boca Raton, FL, 2011).

[14] M.A. Henning and A. Yeo, Total Domination in Graphs (Springer, 2013). doi: 10.1007/978-1-4614-6525-6

[15] IMA-ISU research group on minimum rank (M. Allison, E. Bodine, L.M. DeAlba, J. Debnath, L. DeLoss, C. Garnett, J. Grout, L. Hogben, B. Im, H. Kim, R. Nair, O. Pryporova, K. Savage, B. Shader and A. WangsnessWehe), Minimum rank of skew-symmetric matrices described by a graph, Linear Algebra Appl. 432 (2010) 2457–2472.

[16] N.F. Kingsley, Skew propagation time, Ph.D. Thesis (Iowa State University, 2015). http://lib.dr.iastate.edu/etd/14804/

[17] J.C.-H. Lin, Zero forcing number, Grundy domination number, and their variants, Linear Algebra Appl. 563 (2019) 240–254. doi: 10.1016/j.laa.2018.11.003

[18] S. Mallik and B.L. Shader, On graphs of minimum skew rank 4, Linear Multilinear Algebra 64 (2016) 279–289. doi: 10.1080/03081087.2015.1034642