Back
 OJDM  Vol.6 No.2 , April 2016
The Rupture Degree of Graphs with k-Tree
Abstract: 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.
Cite this paper: Li, Y. , Wang, Q. and Wang, X. (2016) The Rupture Degree of Graphs with k-Tree. Open Journal of Discrete Mathematics, 6, 105-107. doi: 10.4236/ojdm.2016.62011.
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

 
 
Top