Tree cover number and maximum semidefinite nullity of some graph classes

Let G be a graph with a vertex set V and an edge set E consisting of unordered pairs of vertices. The tree cover number of G, denoted τ (G), is the minimum number of vertex disjoint simple trees occurring as induced subgraphs of G that cover all the vertices of G. In this paper, the tree cover number of a line graph τ (L(G)) is shown to be equal to the path number π(G) of G. Also, the tree cover numbers of shadow graphs, corona and Cartesian product of two graphs are found. The graph parameter τ (G) is related to another graph parameter M₊ (G), called the maximum semidefinite nullity of G. Suppose S₊ (G, R) denotes the collection of positive semidefinite real symmetric matrices associated with a given graph G. Then M₊ (G) is the maximum nullity among all matrices in S₊ (G, R). It has been conjectured that τ (G) ≤ M₊ (G). The conjecture is shown to be true for graph classes considered in this work.