A Sufficient Condition for a Graph to Have a k-tree

被引：0
作者：
Aung Kyaw
机构：
[1] Department of Mathematics,
[2] University of Yangon,undefined
[3] Yangon 1104,undefined
[4] Myanmar,undefined
来源：
Graphs and Combinatorics | 2001年 / 17卷
关键词：
Early Result; Span Tree; Connected Graph; Maximum Degree; Maximal Order;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
 A k-tree of a connected graph is a spanning tree with maximum degree at most k. We obtain a sufficient condition for a graph to have a k-tree, as a generalization of the condition of E. Flandrin, H. A. Jung and H. Li [3] for traceability. We also extend early results of Y. Caro, I. Krasikov and Y. Roditty [2] and Min Aung and Aung Kyaw [4] for the maximal order of a tree with bounded maximum degree in a graph.
引用
收藏
页码：113 / 121
页数：8
相关论文
共 29 条
[21]   Efficient associative algorithm to find the least spanning tree of a graph with a node degree constraint [J].
A. Sh. Nepomnyashchaya .
Cybernetics and Systems Analysis, 1998, 34 :77-85
[22]   A Sufficient Condition for Edge Chromatic Critical Graphs to Be HamiltonianAn Approach to Vizing's 2-Factor Conjecture [J].
Luo, Rong ;
Zhao, Yue .
JOURNAL OF GRAPH THEORY, 2013, 73 (04) :469-482
[23]   A new sufficient condition for a tree T to have the (2, 1)-total number Δ+1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta +1$$\end{document} [J].
Qiaojun Shu ;
Weifan Wang ;
Yiqiao Wang .
Journal of Combinatorial Optimization, 2017, 33 (3) :1011-1020
[24]   Fixed points of mappings satisfying contractive condition of integral type in modular spaces endowed with a graph [J].
Mahpeyker Öztürk ;
Mujahid Abbas ;
Ekber Girgin .
Fixed Point Theory and Applications, 2014
[25]   Fixed points of mappings satisfying contractive condition of integral type in modular spaces endowed with a graph [J].
Ozturk, Mahpeyker ;
Abbas, Mujahid ;
Girgin, Ekber .
FIXED POINT THEORY AND APPLICATIONS, 2014,
[26]   Finding the k most vital edges with respect to minimum spanning tree [J].
Hong Shen .
Acta Informatica, 1999, 36 :405-424
[27]   An improved Fan-Type degree condition for k-linked graphs [J].
Dong, Jiuying ;
Li, Xueliang .
ARS COMBINATORIA, 2015, 121 :275-279
[28]   A sufficient condition for a tree to be (Δ+1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(\Delta +1)$$\end{document}-(2,1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(2,1)$$\end{document}-totally labelable [J].
Zhengke Miao ;
Qiaojun Shu ;
Weifan Wang ;
Dong Chen .
Journal of Combinatorial Optimization, 2016, 31 (2) :893-901
[29]   For a graph G and a family of graphs F, the Turan number ex(G, F) is the maximum number of edges an F-free subgraph of G can have. We prove that ex(G, F) ≥ ex(Kr, F) if the chromatic number of G is r and F is a family of connected graphs. This result answers a question raised by Briggs and Cox ["Inverting the Turan problem', Discrete Math. 342(7) (2019), 1865-1884] about the inverse Turan number for all connected graphs. [J].
He, Zhen ;
Lv, Zequn ;
Zhu, Xiutao .
BULLETIN OF THE AUSTRALIAN MATHEMATICAL SOCIETY, 2023, 108 (02) :200-204
123