ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Original Paper

The Erdo″s-So′s conjecture for 2-center spiders

Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2020.03.005
More Information
  • Author Bio:

    WANG Shicheng, male, Master candidate. Research field: Combinatorial graph theory. E-mail: wsc20161@mail.ustc.edu.cn

  • Corresponding author: HOU Xinmin
  • Received Date: 22 May 2019
  • Accepted Date: 28 May 2019
  • Rev Recd Date: 28 May 2019
  • Publish Date: 31 March 2020
    Abstract

  • Abstract

    The Erdo″s-So′s Conjecture states that if G is a graph with average degree more than k-2, then G contains every tree on k vertices. A spider can be seen as a tree with at most one vertex of degree more than two. Fan, Hong, and Liu proved that the conjecture holds for spiders.

    Abstract

    The Erdo″s-So′s Conjecture states that if G is a graph with average degree more than k-2, then G contains every tree on k vertices. A spider can be seen as a tree with at most one vertex of degree more than two. Fan, Hong, and Liu proved that the conjecture holds for spiders.
    • FullText(HTML)
  • loading
    • References(11)
  • [1]
    ERDS P. Extremal Problems in Graph Theory[M]. Fiedler (Ed.), Theory of Graphs and its Applications, Academic Press, 1965: 29-36.
    [2]
    ERDS P, Gallai T. On maximal paths and circuits of graphs[J]. Acta Math. Acad. Sc.i Hungar., 1959, 10: 337-356.
    [3]
    FAN G. The Erds-Sós conjecture for spiders of large size[J]. Discrete mathematics, 2013, 313: 2513-2517.
    [4]
    FAN G, HONG Y, LIU Q. The Erds-Sós conjecture for spiders[J]. Preprint, arXiv:1804.06567, 2018.
    [5]
    FAN G, SUN L. The Erds-Sós conjecture for spiders[J]. Discrete Math., 2007, 307(23): 3055-3062.
    [6]
    MOSER W, PACH J. Recent Developments in Combinatorial Geometry[M]// New Trends in Discrete and Computational Geometry, New York: Springer, 1993.
    [7]
    KALAIG G. Micha perles geometric proof of the Erds-Sós conjecture for caterpillars[EB/OL]. [2018-05-22]https://gilkalai.wordpress.com/2017/08/29/micha-perles-geometric-proof-of-the-erdos-sos-conjecture-for-caterpillars/ (2017). Accessed 19 April 2018.
    [8]
    MCLENNANA. The Erds-Sós Conjecture for trees of diameter four[J]. J. Graph Theory, 2005, 49(4): 291-301.
    [9]
    SIDORENKO A F. Asymptotic soultion for a new class of forbidden r-graphs[J]. Combinatorica, 1989, 9: 207-215.
    [10]
    HOU X, LV C. Bipartite version of the Erds-Sós conjecture[J]. J. Math. Research Appl., in press.
    [11]
    WOZNIAK M. On the Erds-Sós conjecture[J]. J Graph Theory, 1996, 21: 229-234.
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    |
    Get Citation
    PDF
    XML
    [1]
    ERDS P. Extremal Problems in Graph Theory[M]. Fiedler (Ed.), Theory of Graphs and its Applications, Academic Press, 1965: 29-36.
    [2]
    ERDS P, Gallai T. On maximal paths and circuits of graphs[J]. Acta Math. Acad. Sc.i Hungar., 1959, 10: 337-356.
    [3]
    FAN G. The Erds-Sós conjecture for spiders of large size[J]. Discrete mathematics, 2013, 313: 2513-2517.
    [4]
    FAN G, HONG Y, LIU Q. The Erds-Sós conjecture for spiders[J]. Preprint, arXiv:1804.06567, 2018.
    [5]
    FAN G, SUN L. The Erds-Sós conjecture for spiders[J]. Discrete Math., 2007, 307(23): 3055-3062.
    [6]
    MOSER W, PACH J. Recent Developments in Combinatorial Geometry[M]// New Trends in Discrete and Computational Geometry, New York: Springer, 1993.
    [7]
    KALAIG G. Micha perles geometric proof of the Erds-Sós conjecture for caterpillars[EB/OL]. [2018-05-22]https://gilkalai.wordpress.com/2017/08/29/micha-perles-geometric-proof-of-the-erdos-sos-conjecture-for-caterpillars/ (2017). Accessed 19 April 2018.
    [8]
    MCLENNANA. The Erds-Sós Conjecture for trees of diameter four[J]. J. Graph Theory, 2005, 49(4): 291-301.
    [9]
    SIDORENKO A F. Asymptotic soultion for a new class of forbidden r-graphs[J]. Combinatorica, 1989, 9: 207-215.
    [10]
    HOU X, LV C. Bipartite version of the Erds-Sós conjecture[J]. J. Math. Research Appl., in press.
    [11]
    WOZNIAK M. On the Erds-Sós conjecture[J]. J Graph Theory, 1996, 21: 229-234.
    Recommended articles
    TrendMD
    Volume 50 Issue 3 page: 289-293
    Cover

    Article Metrics

    Article views (118) PDF downloads(246)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return