کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648590 | 1342418 | 2009 | 6 صفحه PDF | دانلود رایگان |
We give sufficient conditions for a graph to have degree bounded trees. Let GG be a connected graph and AA a vertex subset of GG. We denote by σk(A)σk(A) the minimum value of the degree sum in GG of any kk independent vertices in AA and by w(G−A)w(G−A) the number of components in the induced subgraph G−AG−A. Our main results are the following: (i) If σk(A)≥|V(G)|−1σk(A)≥|V(G)|−1, then GG contains a tree TT with maximum degree at most kk and A⊆V(T)A⊆V(T). (ii) If σk−w(G−A)(A)≥|A|−1σk−w(G−A)(A)≥|A|−1, then GG contains a spanning tree TT such that dT(x)≤kdT(x)≤k for every x∈Ax∈A. These are generalizations of the result by Win [S. Win, Existenz von Gerüsten mit Vorgeschriebenem Maximalgrad in Graphen, Abh. Math. Sem. Univ. Hamburg 43 (1975) 263–267] and the degree conditions are sharp.
Journal: Discrete Mathematics - Volume 309, Issue 11, 6 June 2009, Pages 3653–3658