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} eq 0$ if ${i,j}in E$ and $a_{ij}=0$ if ${i,j} otin E$. The maximum positive semidefinite nullity of $G$, denoted $operatorname{M}_+(G),$ is $max{operatorname{null}(A)|Ain 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)leq 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 $ngeq 2$ vertices, then $operatorname{M}_+(G)=T(G)leq leftlceilfrac{n}{2}rightrceil$, and if $G$ is a connected outerplanar graph on $ngeq 6$ vertices with no three or four cycle, then $operatorname{M}_+(G)=T(G)leq frac{n}{3}$. We also characterize connected outerplanar graphs with $operatorname{M}_+(G)=T(G)=leftlceilfrac{n}{2}rightrceil.$
تحميل البحث