## Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 678-693 |

Number of pages | 16 |

Journal | Electronic Journal of Linear Algebra |

Volume | 36 |

Issue number | 1 |

State | Published - Sep 2020 |

## Keywords

- Cartesian product graphs
- Corona graphs
- Line graphs
- Maximum semidefinite nullity
- Shadow graphs
- Tree cover number