期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

Some Results on Spanning Trees 被引量：7

Some Results on Spanning Trees
原文传递
导出
摘要 Some structures of spanning trees with many or less leaves in a connected graph are determined.We show（1） a connected graph G has a spanning tree T with minimum leaves such that T contains a longest path,and（2） a connected graph G on n vertices contains a spanning tree T with the maximum leaves such that Δ（G） =Δ（T） and the number of leaves of T is not greater than n D（G）＋1,where D（G） is the diameter of G. Some structures of spanning trees with many or less leaves in a connected graph are determined.We show（1） a connected graph G has a spanning tree T with minimum leaves such that T contains a longest path,and（2） a connected graph G on n vertices contains a spanning tree T with the maximum leaves such that Δ（G） =Δ（T） and the number of leaves of T is not greater than n D（G）＋1,where D（G） is the diameter of G.
作者 Bing Yao Zhong-fu Zhang Jian-fang Wang
机构地区 College of Mathematics and Information Science Academy of Mathematics and Systems Science
出处 《Acta Mathematicae Applicatae Sinica》 SCIE CSCD 2010年第4期607-616,共10页 应用数学学报（英文版）
基金 Supported by the National Natural Science Foundation of China (No.10771091) Project of Knowledge and Science Innovation Program of Northwest Normal University (Grant No.NWNU-KJCXGC-3-47)
关键词 Spanning tree LEAVES DIAMETER Steiner tree independent number Spanning tree leaves diameter Steiner tree independent number
分类号 TP301.6 [自动化与计算机技术—计算机系统结构] O157.5 [理学—基础数学]
  • 相关文献

参考文献14

  • 1Alon, N., Fomin, F.V., Gutin, G., Krivelevich, M., Saurabh, S. Spanning directed trees with many leaves. SIAM Journal on Discrete Mathematics archive, 23(1): 466-476 (2008).
  • 2Bondy-Murty-old Bondy, J.A., Murty, U.S.R. Graph theory with application. Macmillan, New York, 1976.
  • 3Burris, A.C., Schelp, R.H. Vertex-distinguishing proper edge-coloring. J. Graph Theory 26(2): 70-82 (1997).
  • 4Caro, Y., West, D.B., Yuster, R. Connected domination and spanning trees with many leaves. SIAM J. Discrete Math., 13:202-211 (2000).
  • 5Czygrinow, A., Fan, G.H., Hurlbert, G., Kierstead, H.A., William, T. Trotter. Spanning Trees of Bounded Degree. The Electronic Journal of Combinatorics 8:#R33 (2001).
  • 6Ding, G., Johnson, T., Seymour, P. Spanning trees with many leaves. Journal of Graph Theory, 37(4): 189-197 (2001).
  • 7Gallian. J.A. A dynamic survey of graph labeling. The Electronic Journal of Combinatorics, 16:#DS6 (2009).
  • 8Karp, R.M. Reducibility among combinatorial problems. In: Complexity of Computer Computations, Plenum, New York, 1972, 85-103.
  • 9Kleitman, D.J., Douglas B. West, D.B. Spanning trees with many leaves. SIAM Journal on Discrete Mathematics 4:99-106 (1991).
  • 10Linial, N. A lower bound for the circumference of a graph. Discrete Mathematcs, 15:297-300 (1976).

同被引文献45

  • 1HOU JianFeng 1,2,WU JianLiang 2,LIU GuiZhen 2 & LIU Bin 2 1 Center for Discrete Mathematics,Fuzhou University,Fuzhou 350002,China,2 School of Mathematics,Shandong University,Jinan 250100,China.Total coloring of embedded graphs of maximum degree at least ten[J].Science China Mathematics,2010,53(8):2127-2133. 被引量：3
  • 2李珍萍,闫桂英.平面图的循环色数及临界性[J].应用数学学报,2006,29(6):972-983. 被引量：1
  • 3马巧灵,单伟,吴建良.Halin图的有点面约束的边染色[J].山东大学学报（理学版）,2007,42(4):24-27. 被引量：4
  • 4BONDY J A, LOVASZ L. Lengths of cycles in Halin graphs[J].J Graph Theory, 1985,8: 397-410.
  • 5HALIN R. Studies on minimally n-connected graphs [ M]//Comb Math and its applications. London: Academic Press, 1996.
  • 6KRONK H V, MITCHEM J A. Seven-color therom on the sphere[J].Discrete Math, 1973,5(3) : 253-260.
  • 7ZHANG Zhongfu, LIU Linzhong. On the complete chromatic number of Halin-graphs[ J]. Acta Mathematicae Applicatae Sini- ca: English Series. 1997. 13(1):102-106. DOI._ I0. 1007/BF02020485.
  • 8BONDY J A, MURTY U S R. Graph theory with application[M]. New York: Macmillan, 1976.
  • 9BONDY J A. Pancyclic graphs: recent results, infinite and finite sets[J].Colloq Math Soc JOnos Bolyai, 1973, 10:181-187.
  • 10LOVASZ L, PLUMMER M D. On a family of planar bicritical graphs [ J ]. Proceedings of the London Mathematical Society, /975,30 : 160-176.

引证文献7

二级引证文献4

Acta Mathematicae Applicatae Sinica
2010年 第4期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部