Grundy domination and zero forcing in Kneser graphs

被引:14
作者
Bresar, Bostjan [1 ,2 ]
Kos, Tim [2 ]
Daniel Tones, Pablo [3 ,4 ]
机构
[1] Univ Maribor, Fac Nat Sci & Math, Ljubljana, Slovenia
[2] Inst Math Phys & Mech, Ljubljana, Slovenia
[3] Univ Nacl Rosario, Dept Matemat, Rosario, Argentina
[4] Consejo Nacl Invest Cient & Tecn, Rosario, Argentina
关键词
Grundy domination number; Grundy total domination number; Kneser graph; zero forcing number; minimum rank; MINIMUM RANK; INTERSECTION-THEOREMS; SEQUENCES; NUMBER; SYSTEMS; BOUNDS;
D O I
10.26493/1855-3974.1881.384
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
In this paper, we continue the investigation of different types of (Grundy) dominating sequences. We consider four different types of Grundy domination numbers and the related zero forcing numbers, focusing on these numbers in the well-known class of Kneser graphs K-n,K-r. In particular, we establish that the Grundy total domination number gamma(t)(gr) (K-n,K-r) equals ((2r)(r)) for any r >= 2 and n >= 2r + 1. For the Grundy domination number of Kneser graphs we get gamma(gr) (K-n,K-r) = alpha(K-n,K-r) whenever n is sufficiently larger than r. On the other hand, the zero forcing number Z(K-n,K-r) is proved to be ((n)(r)) - ((2r)(r)) when n >= 3r + 1 and r >= 2, while lower and upper bounds are provided for Z(K-n,K-r) when 2r + 1 <= n <= 3r. Some lower bounds for different types of minimum ranks of Kneser graphs are also obtained along the way.
引用
收藏
页码:419 / 430
页数:12
相关论文
共 24 条
[1]   Minimum rank of skew-symmetric matrices described by a graph [J].
Allison, Mary ;
Bodine, Elizabeth ;
DeAlba, Luz Maria ;
Debnath, Joyati ;
DeLoss, Laura ;
Garnett, Colin ;
Grout, Jason ;
Hogben, Leslie ;
Im, Bokhee ;
Kim, Hana ;
Nair, Reshmi ;
Pryporova, Olga ;
Savage, Kendrick ;
Shader, Bryan ;
Wehe, Amy Wangsness .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2010, 432 (10) :2457-2472
[2]   Zero forcing sets and the minimum rank of graphs [J].
Barioli, Francesco ;
Barrett, Wayne ;
Butler, Steve ;
Cioaba, Sebastian M. ;
Cvetkovic, Dragos ;
Fallat, Shaun M. ;
Godsil, Chris ;
Haemers, Willem ;
Hogben, Leslie ;
Mikkelson, Rana ;
Narayan, Sivaram ;
Pryporova, Olga ;
Sciriha, Irene ;
So, Wasin ;
Stevanovic, Dragan ;
van der Holst, Hein ;
Vander Meulen, Kevin N. ;
Wehe, Amy Wangsness .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2008, 428 (07) :1628-1648
[3]   Parameters Related to Tree-Width, Zero Forcing, and Maximum Nullity of a Graph [J].
Barioli, Francesco ;
Barrett, Wayne ;
Fallat, Shaun M. ;
Hall, H. Tracy ;
Hogben, Leslie ;
Shader, Bryan ;
van den Driessche, P. ;
van der Holst, Hein .
JOURNAL OF GRAPH THEORY, 2013, 72 (02) :146-177
[4]   Zero forcing parameters and minimum rank problems [J].
Barioli, Francesco ;
Barrett, Wayne ;
Fallat, Shaun M. ;
Hall, H. Tracy ;
Hogben, Leslie ;
Shader, Bryan ;
van den Driessche, P. ;
van der Holst, Hein .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2010, 433 (02) :401-411
[5]   Total dominating sequences in graphs [J].
Bresar, Batjan ;
Henning, Michael A. ;
Rall, Douglas F. .
DISCRETE MATHEMATICS, 2016, 339 (06) :1665-1676
[6]   Grundy dominating sequences and zero forcing sets [J].
Bresar, Bogtjan ;
Bujtas, Csilla ;
Gologranc, Tanja ;
Klavzar, Sandi ;
Kosmrlj, Gasper ;
Patkos, Balazs ;
Tuza, Zsolt ;
Vizer, Mate .
DISCRETE OPTIMIZATION, 2017, 26 :66-77
[7]   Total dominating sequences in trees, split graphs, and under modular decomposition [J].
Bresar, Bostjan ;
Kos, Tim ;
Nasini, Graciela ;
Torres, Pablo .
DISCRETE OPTIMIZATION, 2018, 28 :16-30
[8]  
Bresar B, 2016, ELECTRON J COMB, V23
[9]   DOMINATING SEQUENCES UNDER ATOMIC CHANGES WITH APPLICATIONS IN SIERPINSKI AND INTERVAL GRAPHS [J].
Bresar, Bostjan ;
Gologranc, Tanja ;
Kos, Tim .
APPLICABLE ANALYSIS AND DISCRETE MATHEMATICS, 2016, 10 (02) :518-531
[10]   Dominating sequences in graphs [J].
Bresar, Bostjan ;
Gologranc, Tanja ;
Milanic, Martin ;
Rall, Douglas F. ;
Rizzi, Romeo .
DISCRETE MATHEMATICS, 2014, 336 :22-36