Vol. 10, No. 5, 2017

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

Volume 11, 1 issue

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
Cover Page
Editorial Board
Editors’ Addresses
Editors’ Interests
About the Journal
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
Subscriptions
Editorial Login
Author Index
Coming Soon
Contacts
 
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
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