|
|||||
 |
|
|
|
|
|
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 , the tree cover number of the graph, denoted , 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 -dimensional hypercube is 2 for all . |
Keywords
tree cover number, hypercube, maximum nullity, minimum rank
|
Mathematical Subject Classification 2010
Primary: 05C05, 05C50, 05C76
|
Supplementary material |
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 |
|
|
