On the tree cover number and the positive semidefinite maximum nullity of a graph

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}\ne 0$ if $\{i,j\}\in E$ and $a_{ij}=0$ if $\{i,j\}\notin E$. The maximum positive semidefinite nullity of $G$, denoted $M_{+}(G),$ is $\max \{\mathrm{null}(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 cardinality of a minimum 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)\le M_{+}(G)$ for all graphs [Barioli et al., Minimum semidefinite rank of outerplanar graphs and the tree cover number, $Elec.J.Lin.Alg.,$ 2011]. We show that the conjecture is true for certain graph families. Furthermore, we prove bounds on $T(G)$ to show that if $G$ is a connected outerplanar graph on $n\ge 2$ vertices, then $M_{+}(G)=T(G)\le \lceil \frac{n}{2}\rceil$, and if $G$ is a connected outerplanar graph on $n\ge 6$ vertices with no three or four cycle, then $M_{+}(G)=T(G)\le \frac{n}{3}$. We also characterize connected outerplanar graphs with $M_{+}(G)=T(G)=\lceil \frac{n}{2}\rceil .$