Tree cover number and maximum semidefinite nullity of some graph classes

Rachel Domagalski, Sivaram K. Narayan

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)678-693
Number of pages16
JournalElectronic Journal of Linear Algebra
Volume36
Issue number1
StatePublished - Sep 2020

Keywords

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

Fingerprint

Dive into the research topics of 'Tree cover number and maximum semidefinite nullity of some graph classes'. Together they form a unique fingerprint.

Cite this