Connections to zero forcing: Tree covers and power domination

Date
2018-01-01
Authors
Bozeman, Chassidy
Major Professor
Advisor
Leslie Hogben
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Mathematics
Organizational Unit
Journal Issue
Series
Department
Mathematics
Abstract

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$).

Comments
Description
Keywords
Citation
DOI
Source