Vol. 10, No. 5, 2017

 Download this article For screen For printing
 Recent Issues
 The Journal About the Journal Editorial Board Subscriptions Editors’ Interests Scientific Advantages Submission Guidelines Submission Form Ethics Statement Editorial Login ISSN: 1944-4184 (e-only) ISSN: 1944-4176 (print) Author Index Coming Soon Other MSP Journals
On the tree cover number of a graph

Chassidy Bozeman, Minerva Catral, Brendan Cook, Oscar E. González and Carolyn Reinhart

Vol. 10 (2017), No. 5, 767–779
Abstract

Given a graph $G$, the tree cover number of the graph, denoted $T\left(G\right)$, is the minimum number of vertex disjoint simple trees occurring as induced subgraphs that cover all the vertices of G. This graph parameter was introduced in 2011 as a tool for studying the maximum positive semidefinite nullity of a graph, and little is known about it. It is conjectured that the tree cover number of a graph is at most the maximum positive semidefinite nullity of the graph.

In this paper, we establish bounds on the tree cover number of a graph, characterize when an edge is required to be in some tree of a minimum tree cover, and show that the tree cover number of the $d$-dimensional hypercube is 2 for all $d\ge 2$.

Keywords
tree cover number, hypercube, maximum nullity, minimum rank
Mathematical Subject Classification 2010
Primary: 05C05, 05C50, 05C76
Supplementary material

Sets used in the proof of Theorem 10

Milestones
Received: 13 November 2015
Revised: 7 September 2016
Accepted: 7 September 2016
Published: 14 May 2017

Communicated by Anant Godbole
Authors
 Chassidy Bozeman Department of Mathematics Iowa State University Ames, IA 50011 United States Minerva Catral Department of Mathematics and Computer Science Xavier University 3000 Victory Parkway Cincinnati, OH 45207 United States Brendan Cook Department of Mathematics Carleton College Northfield, MN 55067 United States Oscar E. González Department of Mathematics University of Puerto Rico San Juan 00931 Puerto Rico Carolyn Reinhart Department of Mathematics University of Minnesota Minneapolis, MN 55455 United States