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 条
  • [11] Topological minors in graphs of large girth
    Kühn, D
    Osthus, D
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2002, 86 (02) : 364 - 380
  • [12] Secret sharing on large girth graphs
    László Csirmaz
    Péter Ligeti
    Cryptography and Communications, 2019, 11 : 399 - 410
  • [13] Secret sharing on large girth graphs
    Csirmaz, Laszlo
    Ligeti, Peter
    CRYPTOGRAPHY AND COMMUNICATIONS-DISCRETE-STRUCTURES BOOLEAN FUNCTIONS AND SEQUENCES, 2019, 11 (03): : 399 - 410
  • [14] Large girth and small oriented diameter graphs
    Cochran, Garner
    DISCRETE MATHEMATICS, 2024, 347 (04)
  • [15] Equitable coloring planar graphs with large girth
    Wu, Jianliang
    Wang, Ping
    DISCRETE MATHEMATICS, 2008, 308 (5-6) : 985 - 990
  • [16] Generation of Cubic Graphs and Snarks with Large Girth
    Brinkmann, Gunnar
    Goedgebeur, Jan
    JOURNAL OF GRAPH THEORY, 2017, 86 (02) : 255 - 272
  • [17] Linear coloring of planar graphs with large girth
    Raspaud, Andre
    Wang, Weifan
    DISCRETE MATHEMATICS, 2009, 309 (18) : 5678 - 5686
  • [18] Generalized signed graphs of large girth and large chromatic number
    Gu, Yangyan
    Qi, Hao
    Yeh, Yeong-Nan
    Zhu, Xuding
    DISCRETE MATHEMATICS, 2022, 345 (10)
  • [19] Improved bounds for topological cliques in graphs of large girth
    Kühn, D
    Osthus, D
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2006, 20 (01) : 62 - 78
  • [20] Odd Induced Subgraphs in Planar Graphs with Large Girth
    Mengjiao Rao
    Jianfeng Hou
    Qinghou Zeng
    Graphs and Combinatorics, 2022, 38
12345