Upper bounds on the k-forcing number of a graph

被引:59
作者
Amos, David [1 ]
Caro, Yair [2 ]
Davila, Randy [3 ]
Pepper, Ryan [4 ]
机构
[1] Texas A&M Univ, College Stn, TX 77843 USA
[2] Univ Haifa, Haifa, Israel
[3] Rice Univ, Houston, TX 77251 USA
[4] Univ Houston Downtown, Houston, TX 77002 USA
关键词
Zero forcing set; Zero forcing number; k-forcing; k-forcing number; Connected dominating sets; Connected domination number; k-independence number; Rank; Nullity; DOMINATION; INDEPENDENCE; SETS;
D O I
10.1016/j.dam.2014.08.029
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Given a simple undirected graph G and a positive integer k, the k-forcing number of G, denoted F-k(G), is the minimum number of vertices that need to be initially colored so that all vertices eventually become colored during the discrete dynamical process described by the following rule. Starting from an initial set of colored vertices and stopping when all vertices are colored: if a colored vertex has at most k non-colored neighbors, then each of its non-colored neighbors becomes colored. When k = 1, this is equivalent to the zero forcing number, usually denoted with Z(G), a recently introduced invariant that gives an upper bound on the maximum nullity of a graph. In this paper, we give several upper bounds on the k-forcing number. Notable among these, we show that if G is a graph with order n >= 2 and maximum degree Delta >= k, then F-k(G) <= (Delta-k+1)n/Delta-k+1+min{delta,k} This simplifies to, for the zero forcing number case of k = 1, Z (G) = F-1 (G) <= Delta n/Delta+1 Moreover, when Delta >= 2 and the graph is k-connected, we prove that F-k(G) <= (Delta-2)n+2/Delta+k-2 which is an improvement when k <= 2, and specializes to, for the zero forcing number case, Z(G) = F-1 (G) <= (Delta-2)n+2/Delta-1. These results resolve a problem posed by Meyer about regular bipartite circulant graphs. Finally, we present a relationship between the k-forcing number and the connected k-domination number. As a corollary, we find that the sum of the zero forcing number and connected domination number is at most the order for connected graphs. (C) 2014 Elsevier B.V. All rights reserved.
引用
收藏
页码:1 / 10
页数:10
相关论文
共 24 条
[1]   On the k-residue of disjoint unions of graphs with applications to k-independence [J].
Amos, David ;
Davila, Randy ;
Pepper, Ryan .
DISCRETE MATHEMATICS, 2014, 321 :24-34
[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]   Full control by locally induced relaxation [J].
Burgarth, Daniel ;
Giovannetti, Vittorio .
PHYSICAL REVIEW LETTERS, 2007, 99 (10)
[4]   Connected domination and spanning trees with many leaves [J].
Caro, Y ;
West, DB ;
Yuster, R .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2000, 13 (02) :202-211
[5]  
Caro Y, 2014, AUSTRALAS J COMB, V59, P1
[6]  
Caro Yair, 2014, DISCRETE MA IN PRESS
[7]   k-Domination and k-Independence in Graphs: A Survey [J].
Chellali, Mustapha ;
Favaron, Odile ;
Hansberg, Adriana ;
Volkmann, Lutz .
GRAPHS AND COMBINATORICS, 2012, 28 (01) :1-55
[8]  
Chilakamarri K.B., 2012, B I COMBIN APPL, V64, P57
[9]  
DeLaVina Ermelinda, 2012, C NUMER, V213, P185
[10]   Irreversible k-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion [J].
Dreyer, Paul A., Jr. ;
Roberts, Fred S. .
DISCRETE APPLIED MATHEMATICS, 2009, 157 (07) :1615-1627