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 条
  • [1] A proof of a conjecture on the Randic index of graphs with given girth
    Li, Xueliang
    Liu, Jianxi
    DISCRETE APPLIED MATHEMATICS, 2009, 157 (15) : 3332 - 3335
  • [2] Gallai's Conjecture For Graphs of Girth at Least Four
    Harding, Peter
    McGuinness, Sean
    JOURNAL OF GRAPH THEORY, 2014, 75 (03) : 256 - 274
  • [3] The Erdos-Sos conjecture for graphs of girth 5
    Brandt, S
    Dobson, E
    DISCRETE MATHEMATICS, 1996, 150 (1-3) : 411 - 414
  • [4] LIGHT GRAPHS IN PLANAR GRAPHS OF LARGE GIRTH
    Hudak, Peter
    Macekova, Maria
    Madaras, Tomas
    Siroczki, Pavol
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2016, 36 (01) : 227 - 238
  • [5] Domination and total domination in cubic graphs of large girth
    Dantas, Simone
    Joos, Felix
    Loewenstein, Christian
    Machado, Deiwison S.
    Rautenbach, Dieter
    DISCRETE APPLIED MATHEMATICS, 2014, 174 : 128 - 132
  • [6] Connectivity Keeping Trees in 2-Connected Graphs with Girth Conditions
    Hasunuma, Toru
    COMBINATORIAL ALGORITHMS, IWOCA 2020, 2020, 12126 : 316 - 329
  • [7] Connectivity Keeping Trees in 2-Connected Graphs with Girth Conditions
    Toru Hasunuma
    Algorithmica, 2021, 83 : 2697 - 2718
  • [8] Odd Induced Subgraphs in Planar Graphs with Large Girth
    Rao, Mengjiao
    Hou, Jianfeng
    Zeng, Qinghou
    GRAPHS AND COMBINATORICS, 2022, 38 (04)
  • [9] Connectivity Keeping Trees in 2-Connected Graphs with Girth Conditions
    Hasunuma, Toru
    ALGORITHMICA, 2021, 83 (09) : 2697 - 2718
  • [10] ON COLOURING ORIENTED GRAPHS OF LARGE GIRTH
    Kayll, P. Mark
    Morris, Michael
    CONTRIBUTIONS TO DISCRETE MATHEMATICS, 2023, 18 (02) : 234 - 243
12345