Vol. 10, No. 5, 2017

Download this article
Download this article For screen
For printing
Recent Issues

Volume 17
Issue 4, 543–722
Issue 3, 363–541
Issue 2, 183–362
Issue 1, 1–182

Volume 16, 5 issues

Volume 15, 5 issues

Volume 14, 5 issues

Volume 13, 5 issues

Volume 12, 8 issues

Volume 11, 5 issues

Volume 10, 5 issues

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
About the journal
Ethics and policies
Peer-review process
 
Submission guidelines
Submission form
Editorial board
Editors' interests
 
Subscriptions
 
ISSN 1944-4184 (online)
ISSN 1944-4176 (print)
 
Author index
To appear
 
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(G), 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 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