A k-tree of a connected graph G is a spanning tree with maximum degree
at most k. The rupture degree for a
connected graph G is defined by , where and ,
respectively, denote the order of the largest component and number of
components in . In this
paper, we show that for a connected graph G,
if ？for any cut-set , then G has a k-tree.
References
[1]
Win, S. (1975) Existenz von gerusten mit vorgeschriebenen maximalgrad in graphen. Adhandlungen aus den Mathematischen Seminor der Universitat Hamburg, 43, 263-267. http://dx.doi.org/10.1007/BF02995957
[2]
Aung, M. and Kyaw, A. (1998) Maximal Trees with Bounded Maximum Degree in a Graph. Graphs and Combinatorics, 14, 209-221. http://dx.doi.org/10.1007/s003730050027
[3]
Kyaw, A. (2001) A Sufficient Condition for a Graph to Have a k-Tree. Graphs and Combinatorics, 14, 113-121. http://dx.doi.org/10.1007/s003730170059
[4]
Li, Y., Zhang, S. and Li, X. (2005) The Rupture Degree of Graphs. International Journal of Computer Mathematics, 82, 793-803. http://dx.doi.org/10.1080/00207160412331336062
[5]
Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications. Macmillan London and Elsevier, New York. http://dx.doi.org/10.1007/978-1-349-03521-2
![\"\"](\"Edit_b58fa23a-98ff-4199-911e-76bc4b4ef859.bmp\")
![\"\"](\"Edit_35922f6e-2272-4632-87a9-ed52c8561fe6.bmp\")
![\"\"](\"Edit_e6b09751-5959-4a77-b685-17d31303ae86.bmp\")
![\"\"](\"Edit_077131f4-f132-41b4-a5cd-66b88bc66cf9.bmp\")
![\"\"](\"Edit_e19ec7e8-d1ad-4c74-866c-373648242933.bmp\")
？![\"\"](\"Edit_1a990dd6-5334-49a4-89cb-736f7a80aa19.bmp\")
