On a conjecture about trees in graphs with large girth

被引：3
|
作者：
Jiang, T [1 ]
机构：
[1] Michigan Technol Univ, Dept Math Sci, Houghton, MI 49931 USA
来源：
JOURNAL OF COMBINATORIAL THEORY SERIES B | 2001年 / 83卷 / 02期
关键词：
trees; girth;
D O I：
10.1006/jctb.2001.2049
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
The girth of a graph G is the length of a shortest cycle in G. Dobson (1994. Ph.D. dissertation, Louisiana State University, Baton Rouge, LA) conjectured that every graph G with girth at least 2t + 1 and minimum degree at least k/t contains every tree T with k edges whose maximum degree does not exceed the minimum degree of G. The conjecture has been proved for t less than or equal to3. In this paper, we prove Dobson's conjecture. (C) 2001 Academic Press.
引用
收藏
页码：221 / 232
页数：12
相关论文
共 50 条
  • [21] Acyclic chromatic indices of planar graphs with large girth
    Wang, Weifan
    Shu, Qiaojun
    Wang, Kan
    Wang, Ping
    DISCRETE APPLIED MATHEMATICS, 2011, 159 (12) : 1239 - 1253
  • [22] Graphs of large girth with prescribed partial circular colourings
    Pan, ZS
    Zhu, XD
    GRAPHS AND COMBINATORICS, 2005, 21 (01) : 119 - 129
  • [23] Graphs of Large Girth with Prescribed Partial Circular Colourings
    Zhishi Pan
    Xuding Zhu
    Graphs and Combinatorics, 2005, 21 : 119 - 129
  • [24] On a construction of graphs with high chromatic capacity and large girth
    Zhou, Bing
    DISCRETE MATHEMATICS, 2010, 310 (17-18) : 2452 - 2454
  • [25] Infinite highly connected planar graphs of large girth
    Georgakopoulos, A.
    ABHANDLUNGEN AUS DEM MATHEMATISCHEN SEMINAR DER UNIVERSITAT HAMBURG, 2006, 76 (1): : 235 - 245
  • [26] Acyclic edge coloring of planar graphs with large girth
    Yu, Dongxiao
    Hou, Jianfeng
    Liu, Guizhen
    Liu, Bin
    Xu, Lan
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (47-49) : 5196 - 5200
  • [27] Infinite highly connected planar graphs of large girth
    A. Georgakopoulos
    Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 2006, 76 : 235 - 245
  • [28] On The Harmonic Index and The Girth for Graphs
    Zhong, Lingping
    ROMANIAN JOURNAL OF INFORMATION SCIENCE AND TECHNOLOGY, 2013, 16 (04): : 253 - 260
  • [29] Strong edge-coloring for planar graphs with large girth
    Chen, Lily
    Deng, Kecai
    Yu, Gexin
    Zhou, Xiangqian
    DISCRETE MATHEMATICS, 2019, 342 (02) : 339 - 343
  • [30] Domination in Graphs of Minimum Degree at least Two and Large Girth
    Christian Löwenstein
    Dieter Rautenbach
    Graphs and Combinatorics, 2008, 24 : 37 - 46
12345