Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650429 | Discrete Mathematics | 2008 | 5 Pages |
Abstract
The purpose of this paper is to initiate study of the following problem: Let G be a graph, and k⩾1k⩾1. Determine the minimum number s of trees T1,…,TsT1,…,Ts, Δ(Ti)⩽k,i=1,…,sΔ(Ti)⩽k,i=1,…,s, covering all vertices of GG. We conjecture: Let G be a connected graph, and k⩾2k⩾2. Then the vertices of G can be covered by s⩽n-δδ(k-1)+1 edge-disjoint trees of maximum degree ⩽k⩽k. As a support for the conjecture we prove the statement for some values of δδ and kk.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
P. Horak, K. McAvaney,