Connections to zero forcing: Tree covers and power domination

Bozeman, Chassidy
Journal Title
Journal ISSN
Volume Title
Research Projects
Organizational Units
Organizational Unit
Journal Issue

For a simple graph $G=(V,E),$ let $\mathcal{S}_+(G)$ denote the set of real positive semidefinite matrices $A=(a_{ij})$ such that $a_{ij}\neq 0$ if $\{i,j\}\in E$, $a_{ij}=0$ if $\{i,j\}\notin E$, and $a_{ii}$ is any real number. The maximum positive semidefinite nullity of $G$, denoted $\Mp(G),$ is $\max\{\nullity(A)|A\in \mathcal{S}_+(G)\}.$ A tree cover of $G$ is a collection of vertex-disjoint simple trees occurring as induced subgraphs of $G$ that cover all the vertices of $G$. The tree cover number of $G$, denoted $T(G)$, is the minimum cardinality of a tree cover. It is known that the tree cover number of a graph and the maximum positive semidefinite nullity of a graph are equal for outerplanar graphs, and it was conjectured in 2011 that $T(G)\leq \Mp(G)$ for all graphs [Barioli et al., Minimum semidefinite rank of outerplanar graphs and the tree cover number, {\em Elec. J. Lin. Alg.,} 2011]. We prove bounds on $T(G)$ to show that if $G$ is a connected outerplanar graph on $n\geq 2$ vertices, then $\Mp(G)=T(G)\leq \left\lceil\frac{n}{2}\right\rceil$, and if $G$ is a connected outerplanar graph on $n\geq 6$ vertices with no three or four cycle, then $\Mp(G)=T(G)\leq \frac{n}{3}$. We characterize connected outerplanar graphs with $\Mp(G)=T(G)=\left\lceil\frac{n}{2}\right\rceil,$ and for each cactus graph $G$, we give a formula for computing $T(G)$ (and therefore $\Mp(G)$). Furthermore, we show that if $G$ is a connected graph on $n$ vertices and at least $2n$ edges, then $T(L(G))\leq \Mp(L(G))$, where $L(G)$ denotes the line graph of $G$, and we give inequalities involving $T(G)$ and other graph parameters.

Furthermore, we give Nordhaus-Gaddum upper and lower bounds on the sum of the power propagation time of a graph and its complement, and we consider the effects of edge subdivisions and edge contractions on the power propagation time of a graph. We also study a generalization of power propagation time, known as $k-$power propagation time, by characterizing all simple graphs on $n$ vertices whose $k-$power propagation time is $n-1$ or $n-2$ (for $k\geq 1$) and $n-3$ (for $k\geq 2$). We determine all trees on $n$ vertices whose power propagation time ($k=1$) is $n-3$, and give partial characterizations of graphs whose $k-$power propagation time is equal to 1 (for $k\geq 1$).

combinatorial matrix theory, graph theory, Power domination, Tree covers