Article ID Journal Published Year Pages File Type
4650429 Discrete Mathematics 2008 5 Pages PDF
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.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,