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
    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
    [J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2010, 432 (10) : 2457 - 2472
  • [2] Zero forcing sets and the minimum rank of graphs
    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
    [J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2008, 428 (07) : 1628 - 1648
  • [3] Parameters Related to Tree-Width, Zero Forcing, and Maximum Nullity of a Graph
    Barioli, Francesco
    Barrett, Wayne
    Fallat, Shaun M.
    Hall, H. Tracy
    Hogben, Leslie
    Shader, Bryan
    van den Driessche, P.
    van der Holst, Hein
    [J]. JOURNAL OF GRAPH THEORY, 2013, 72 (02) : 146 - 177
  • [4] Zero forcing parameters and minimum rank problems
    Barioli, Francesco
    Barrett, Wayne
    Fallat, Shaun M.
    Hall, H. Tracy
    Hogben, Leslie
    Shader, Bryan
    van den Driessche, P.
    van der Holst, Hein
    [J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2010, 433 (02) : 401 - 411
  • [5] Total dominating sequences in graphs
    Bresar, Batjan
    Henning, Michael A.
    Rall, Douglas F.
    [J]. DISCRETE MATHEMATICS, 2016, 339 (06) : 1665 - 1676
  • [6] Grundy dominating sequences and zero forcing sets
    Bresar, Bogtjan
    Bujtas, Csilla
    Gologranc, Tanja
    Klavzar, Sandi
    Kosmrlj, Gasper
    Patkos, Balazs
    Tuza, Zsolt
    Vizer, Mate
    [J]. DISCRETE OPTIMIZATION, 2017, 26 : 66 - 77
  • [7] Total dominating sequences in trees, split graphs, and under modular decomposition
    Bresar, Bostjan
    Kos, Tim
    Nasini, Graciela
    Torres, Pablo
    [J]. 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
    Bresar, Bostjan
    Gologranc, Tanja
    Kos, Tim
    [J]. APPLICABLE ANALYSIS AND DISCRETE MATHEMATICS, 2016, 10 (02) : 518 - 531
  • [10] Dominating sequences in graphs
    Bresar, Bostjan
    Gologranc, Tanja
    Milanic, Martin
    Rall, Douglas F.
    Rizzi, Romeo
    [J]. DISCRETE MATHEMATICS, 2014, 336 : 22 - 36