Families of graphs with maximum nullity equal to zero forcing number

被引:3
作者
Alameda, Joseph S. [1 ]
Curl, Emelie [1 ]
Grez, Armando [1 ]
Hogben, Leslie [1 ,2 ]
Kingston, O'Neill [1 ]
Schulte, Alex [1 ]
Young, Derek [1 ]
Young, Michael [1 ]
机构
[1] Iowa State Univ, Dept Math, Ames, IA 50011 USA
[2] Amer Inst Math, 600 E Brokaw Rd, San Jose, CA 95112 USA
来源
SPECIAL MATRICES | 2018年 / 6卷 / 01期
基金
美国国家科学基金会;
关键词
zero forcing number; maximum nullity; semiregular bipartite graph; Generalized Petersen graph;
D O I
10.1515/spma-2018-0006
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
The maximum nullity of a simple graph G, denoted M(G), is the largest possible nullity over all symmetric real matrices whose ijth entry is nonzero exactly when {i,j} is an edge in G for i not equal j, and the iith entry is any real number. The zero forcing number of a simple graph G, denoted Z(G), is the minimum number of blue vertices needed to force all vertices of the graph blue by applying the color change rule. This research is motivated by the longstanding question of characterizing graphs G for which M(G) = Z(G). The following conjecture was proposed at the 2017 AIM workshop Zero forcing and its applications: If G is a bipartite 3 semiregular graph, then M(G) = Z(G). A counterexample was found by J. C.-H. Lin but questions remained as to which bipartite 3-semiregular graphs have M(G) = Z(G). We use various tools to find bipartite families of graphs with regularity properties for which the maximum nullity is equal to the zero forcing number; most are bipartite 3-semiregular. In particular, we use the techniques of twinning and vertex sums to form new families of graphs for which M(G) = Z(G) and we additionally establish M(G) = Z(G) for certain Generalized Petersen graphs.
引用
收藏
页码:56 / 67
页数:12
相关论文
共 11 条
  • [1] [Anonymous], 2017, AIM WORKSH ZER FORC
  • [2] Computation of minimal rank and path cover number for certain graphs
    Barioli, F
    Fallat, S
    Hogben, L
    [J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2004, 392 : 289 - 303
  • [3] 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
  • [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] An upper bound for the minimum rank of a graph
    Berman, Avi
    Friedland, Shmuel
    Hogben, Leslie
    Rothblum, Uriel G.
    Shader, Bryan
    [J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2008, 429 (07) : 1629 - 1638
  • [6] Butler S., SAGE PROGRAMS CALCUL
  • [7] Techniques for determining the minimum rank of a small graph
    DeLoss, Laura
    Grout, Jason
    Hogben, Leslie
    McKay, Tracy
    Smith, Jason
    Tims, Geoff
    [J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2010, 432 (11) : 2995 - 3001
  • [8] Lin James, COMMUNICATION
  • [9] A technique for computing the zero forcing number of a graph with a cut-vertex
    Row, Darren D.
    [J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2012, 436 (12) : 4423 - 4432
  • [10] Maximum nullity of outerplanar graphs and the path cover number
    Sinkovic, John
    [J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2010, 432 (08) : 2052 - 2060