# Minimum Rank, Maximum Nullity, and Zero Forcing of Graphs (13frg164)

Arriving in Banff, Alberta Sunday, June 16 and departing Sunday June 23, 2013

## Objectives

There are two objectives of this proposed Focused Research Group. The first is to study the relationship between the maximum nullity and zero forcing number of

complete subdivision graphs. Let $e=uv$ be an edge of $G$. Define $G_e$ to be the graph obtained from $G$ by inserting a new vertex $w$ into $V$, deleting the edge $e$ and inserting edges $uw$ and $wv$. We say that that the

edge $e$ has been subdivided and call $G_e$ an edge subdivision of $G$. A complete subdivision graph $s(G)$ is obtained from a graph $G$ by subdividing every edge of $G$ exactly once. In [wayne09] and [O], the authors investigate the maximum nullity and zero forcing number of graphs obtained by a finite number of edge subdivisions of a given graph and, among other results, establish results on the effect subdividing an edge has on the graph's zero

forcing number and maximum nullity. It is known that there exists a graph $G$ such that $M(G) < Z(G)$. In fact, there exists graphs $G$ such that $M(G_e) < Z(G_e)$ for some edge $e in G$. However, it is conjectured in [CCetal] for all graphs $G$, $M(s(G)) = Z(s(G))$. For certain classes of graphs, the conjecture has been proven to be true in [wayne09] and [CCetal].

The second objective is to make progress on the Graph Complement Conjecture (GCC) for minimum rank and other Nordhaus-Gaddum type problems related to minimum rank and maximum nullity. We denote the complement of $G$ by $overline{G}$. The GCC, which arose from the 2006 AIM workshop [AIM06], states: For any graph $G$, $mr(G) + mr( overline{G} ) le |G| + 2$. (see [BHS07]). A stronger variant of the GCC involving the Colin de Verdi`ere number $mu$ had been conjectured previously [KLV97]. Several other stronger variants have been conjectured recently and numerous partial results supporting the conjectures have been obtained [BBetal]. However, it remains unresolved at present. Note that the analogous conjecture for zero forcing number, i.e. $Z(G) + Z( overline

{G} ) le |G| - 2$, has recently been established [EEetal].

The GCC and its variants are what graph theorists call Nordhaus-Gaddum type problems, in that they involve bounding the sum of a graph parameter evaluated at a graph $G$ and its complement $overline{G}$. Nordhaus-Gaddum type problems have been studied for many different graph parameters, including chromatic

number, independence number, domination number, Hadwiger number, etc. (see, for example, [CN71]).

Because of the recent progress on each of these problems (see [CCetal], [wayne09], [BBetal]), the time is right to attack these conjectures. The proposed focused research group brings together a group of people with the necessary expertise to make significant progress on these conjectures.

References:

[AIM06] American Institute of Mathematics workshop,

``Spectra of Families of Matrices described by Graphs, Digraphs,

and Sign Patterns,"

held Oct. 23-27, 2006 in Palo Alto, CA. {tt http://aimath.org/pastworkshops/matrixspectrum.html}

[AIM08]

AIM Minimum

Rank -- Special Graphs Work Group. Zero forcing sets

and the minimum rank of graphs, Linear Algebra and its

Applications, 428: 1628-1648, (2008).

[BBetal] F. Barioli, W. Barrett, S. Fallat,

H. T. Hall, L. Hogben, H. van der Holst.

On the Graph Complement Conjecture Associated with Minimum Rank.

{em Linear Algebra and its Applications}, 436: 4373--4391, 2012.

[BHS07] R. Brualdi, L. Hogben, B. Shader,

AIM Workshop on Spectra of Families of Matrices Described by Graphs,

Digraphs and Sign

Patterns, Final report: Mathematical Results, 2007.

{tt http://aimath.org/pastworkshops/matrixspectrumrep.pdf}.

[CCetal] M. Catral, A. Cepek, L. Hogben, M. Huynh, K. Lazebnik,

T. Peters, and M. Young. Zero Forcing Number, Maximum

Nullity, and Path Cover Number of Subdivided Graphs,

Discrete Applied Mathematics 160, 1994-2005, (2012).

[CN71] G. Chartrand and J. Mitchem.

Graphical theorems of the Nordhaus-Gaddum class.

{em Recent Trends in Graph Theory}, Lecture Notes in Mathematics 186, Springer, Berlin, 1971: 55-61.

[EEetal] J. Ekstrand, C. Erickson, H. T. Hall, D. Hay, L. Hogben, R. Johnson, N. Kingsley, S. Osborne, T. Peters, J. Roat, A. Ross, D. D. Row, N. Warnberg, M. Young. Positive semidefinite zero forcing.

Under review.

[FH07] S. Fallat, L. Hogben. The minimum rank of symmetric

matrices described by a graph: A survey.

Linear

Algebra and its Applications, 426: 558-582, (2007).

[FH13] S. Fallat and L. Hogben. Minimum Rank, Maximum

Nullity, and Zero Forcing Number of Graphs. To appear

in Handbook of Linear Algebra 2nd Edition, L.

Hogben, Editor, Chapman & Hall$char92$CRC Press,

Boca Raton, (2013).

[KLV97] A. Kotlov, L. Lov{'a}sz, S. Vempala. The Colin de Verd`ere number and sphere representations of a graph. textit{Combinatorica} {17}: 483--521, 1997.

[O] K. Owens.

Properties of the zero forcing number. Master's

Thesis, Brigham Young University, (2009).

[wayne09] W.

Barrett, R. Bowcutt, M. Cutler, S. Gibelyou, K. Owens.

Minimum rank of edge subdivisions of graphs, Electron.

J. Linear Algebra, 18: 530-563, (2009).

complete subdivision graphs. Let $e=uv$ be an edge of $G$. Define $G_e$ to be the graph obtained from $G$ by inserting a new vertex $w$ into $V$, deleting the edge $e$ and inserting edges $uw$ and $wv$. We say that that the

edge $e$ has been subdivided and call $G_e$ an edge subdivision of $G$. A complete subdivision graph $s(G)$ is obtained from a graph $G$ by subdividing every edge of $G$ exactly once. In [wayne09] and [O], the authors investigate the maximum nullity and zero forcing number of graphs obtained by a finite number of edge subdivisions of a given graph and, among other results, establish results on the effect subdividing an edge has on the graph's zero

forcing number and maximum nullity. It is known that there exists a graph $G$ such that $M(G) < Z(G)$. In fact, there exists graphs $G$ such that $M(G_e) < Z(G_e)$ for some edge $e in G$. However, it is conjectured in [CCetal] for all graphs $G$, $M(s(G)) = Z(s(G))$. For certain classes of graphs, the conjecture has been proven to be true in [wayne09] and [CCetal].

The second objective is to make progress on the Graph Complement Conjecture (GCC) for minimum rank and other Nordhaus-Gaddum type problems related to minimum rank and maximum nullity. We denote the complement of $G$ by $overline{G}$. The GCC, which arose from the 2006 AIM workshop [AIM06], states: For any graph $G$, $mr(G) + mr( overline{G} ) le |G| + 2$. (see [BHS07]). A stronger variant of the GCC involving the Colin de Verdi`ere number $mu$ had been conjectured previously [KLV97]. Several other stronger variants have been conjectured recently and numerous partial results supporting the conjectures have been obtained [BBetal]. However, it remains unresolved at present. Note that the analogous conjecture for zero forcing number, i.e. $Z(G) + Z( overline

{G} ) le |G| - 2$, has recently been established [EEetal].

The GCC and its variants are what graph theorists call Nordhaus-Gaddum type problems, in that they involve bounding the sum of a graph parameter evaluated at a graph $G$ and its complement $overline{G}$. Nordhaus-Gaddum type problems have been studied for many different graph parameters, including chromatic

number, independence number, domination number, Hadwiger number, etc. (see, for example, [CN71]).

Because of the recent progress on each of these problems (see [CCetal], [wayne09], [BBetal]), the time is right to attack these conjectures. The proposed focused research group brings together a group of people with the necessary expertise to make significant progress on these conjectures.

References:

[AIM06] American Institute of Mathematics workshop,

``Spectra of Families of Matrices described by Graphs, Digraphs,

and Sign Patterns,"

held Oct. 23-27, 2006 in Palo Alto, CA. {tt http://aimath.org/pastworkshops/matrixspectrum.html}

[AIM08]

AIM Minimum

Rank -- Special Graphs Work Group. Zero forcing sets

and the minimum rank of graphs, Linear Algebra and its

Applications, 428: 1628-1648, (2008).

[BBetal] F. Barioli, W. Barrett, S. Fallat,

H. T. Hall, L. Hogben, H. van der Holst.

On the Graph Complement Conjecture Associated with Minimum Rank.

{em Linear Algebra and its Applications}, 436: 4373--4391, 2012.

[BHS07] R. Brualdi, L. Hogben, B. Shader,

AIM Workshop on Spectra of Families of Matrices Described by Graphs,

Digraphs and Sign

Patterns, Final report: Mathematical Results, 2007.

{tt http://aimath.org/pastworkshops/matrixspectrumrep.pdf}.

[CCetal] M. Catral, A. Cepek, L. Hogben, M. Huynh, K. Lazebnik,

T. Peters, and M. Young. Zero Forcing Number, Maximum

Nullity, and Path Cover Number of Subdivided Graphs,

Discrete Applied Mathematics 160, 1994-2005, (2012).

[CN71] G. Chartrand and J. Mitchem.

Graphical theorems of the Nordhaus-Gaddum class.

{em Recent Trends in Graph Theory}, Lecture Notes in Mathematics 186, Springer, Berlin, 1971: 55-61.

[EEetal] J. Ekstrand, C. Erickson, H. T. Hall, D. Hay, L. Hogben, R. Johnson, N. Kingsley, S. Osborne, T. Peters, J. Roat, A. Ross, D. D. Row, N. Warnberg, M. Young. Positive semidefinite zero forcing.

Under review.

[FH07] S. Fallat, L. Hogben. The minimum rank of symmetric

matrices described by a graph: A survey.

Linear

Algebra and its Applications, 426: 558-582, (2007).

[FH13] S. Fallat and L. Hogben. Minimum Rank, Maximum

Nullity, and Zero Forcing Number of Graphs. To appear

in Handbook of Linear Algebra 2nd Edition, L.

Hogben, Editor, Chapman & Hall$char92$CRC Press,

Boca Raton, (2013).

[KLV97] A. Kotlov, L. Lov{'a}sz, S. Vempala. The Colin de Verd`ere number and sphere representations of a graph. textit{Combinatorica} {17}: 483--521, 1997.

[O] K. Owens.

Properties of the zero forcing number. Master's

Thesis, Brigham Young University, (2009).

[wayne09] W.

Barrett, R. Bowcutt, M. Cutler, S. Gibelyou, K. Owens.

Minimum rank of edge subdivisions of graphs, Electron.

J. Linear Algebra, 18: 530-563, (2009).