Grundy Domination and Zero Forcing in Regular Graphs

被引:2
作者
Bresar, Bostjan [1 ,2 ]
Brezovnik, Simon [1 ,3 ]
机构
[1] Univ Maribor, Fac Nat Sci & Math, Maribor, Slovenia
[2] Inst Math Phys & Mech, Ljubljana, Slovenia
[3] Univ Maribor, Fac Educ, Maribor, Slovenia
关键词
Grundy domination number; Zero forcing; Regular graph; Cubic graph; SEQUENCES; NUMBER; BOUNDS;
D O I
10.1007/s40840-021-01134-7
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Given a finite graph G, the maximum length of a sequence (v(1), ..., v(k)) of vertices in G such that each v(i) dominates a vertex that is not dominated by any vertex in {v(1), ..., v(i-1)} is called the Grundy domination number, gamma(gr)(G), of G. A small modification of the definition yields the Z-Grundy domination number, which is the dual invariant of the well-known zero forcing number. In this paper, we prove that gamma(gr)(G) >= n+inverted right perpendiculark/2inverted left perpendicular-2/k-1 holds for every connected k-regular graph of order n different from Kk+1 and (2C(4)) over bar. The bound in the case k = 3 reduces to gamma(gr)(G) >= n/2, and we characterize the connected cubic graphs with gamma(gr)(G) = n/2. If G is different from K-4 and K-3,K-3, then n/2 is also an upper bound for the zero forcing number of a connected cubic graph, and we characterize the connected cubic graphs attaining this bound.
引用
收藏
页码:3637 / 3661
页数:25
相关论文
共 23 条
[1]   Upper bounds on the k-forcing number of a graph [J].
Amos, David ;
Caro, Yair ;
Davila, Randy ;
Pepper, Ryan .
DISCRETE APPLIED MATHEMATICS, 2015, 181 :1-10
[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]  
Benson KF, 2018, AUSTRALAS J COMB, V70, P221
[6]   Total dominating sequences in graphs [J].
Bresar, Batjan ;
Henning, Michael A. ;
Rall, Douglas F. .
DISCRETE MATHEMATICS, 2016, 339 (06) :1665-1676
[7]   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
[8]   Grundy domination and zero forcing in Kneser graphs [J].
Bresar, Bostjan ;
Kos, Tim ;
Daniel Tones, Pablo .
ARS MATHEMATICA CONTEMPORANEA, 2019, 17 (02) :419-430
[9]  
Bresar B, 2016, ELECTRON J COMB, V23
[10]   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