Research ArticleOpen AccessGoogle Scholar indexed
The Rupture Degree of Graphs with <i>k</i>-Tree
College of Mathematics and Statistics, Qinghai Nationalities University, Xining, China
College of Mathematics and Statistics, Qinghai Nationalities University, Xining, China
College of Mathematics and Statistics, Qinghai Nationalities University, Xining, China
- 1 College of Mathematics and Statistics, Qinghai Nationalities University, Xining, China
- 2 College of Mathematics and Statistics, Qinghai Nationalities University, Xining, China
- 3 College of Mathematics and Statistics, Qinghai Nationalities University, Xining, China
Open Journal of Discrete Mathematics·Volume 06 (2016)·Pages 105–107·Published 31 March 2016·DOI10.4236/ojdm.2016.62011
Copy link · social · email
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.
KeywordsThe Rupture Degree<i>k</i>-TreeInduced Graph
- 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
- 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
- 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
- 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
- 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