Ramsey numbers of trees versus fans

Yanbo Zhang, Haitze J. Broersma, Yaojun Chen

    Research output: Contribution to journalArticleAcademicpeer-review

    2 Citations (Scopus)
    18 Downloads (Pure)

    Abstract

    For two given graphs G1 and G2, the Ramsey number R(G1, G2) is the smallest integerN such that, for any graph G of order N, either G contains G1 as a subgraph or the complement of G contains G2 as a subgraph. Let Tn be a tree of order n, Sn a star of order n, and Fm a fan of order 2m + 1, i.e., m triangles sharing exactly one vertex. In this paper, we prove that R(Tn, Fm) = 2n − 1 for n ≥ 3m^2 − 2m − 1, and if Tn = Sn, then the range can be replaced by n ≥ max{m(m − 1) + 1, 6(m − 1)}, which is tight in some sense.
    Original languageUndefined
    Pages (from-to)994-999
    Number of pages6
    JournalDiscrete mathematics
    Volume338
    Issue number6
    DOIs
    Publication statusPublished - Jun 2015

    Keywords

    • Tree
    • Star
    • Fan
    • Ramsey number

    Cite this

    Zhang, Yanbo ; Broersma, Haitze J. ; Chen, Yaojun. / Ramsey numbers of trees versus fans. In: Discrete mathematics. 2015 ; Vol. 338, No. 6. pp. 994-999.
    @article{97be4a5f221842c6905fb9afd057d5f7,
    title = "Ramsey numbers of trees versus fans",
    abstract = "For two given graphs G1 and G2, the Ramsey number R(G1, G2) is the smallest integerN such that, for any graph G of order N, either G contains G1 as a subgraph or the complement of G contains G2 as a subgraph. Let Tn be a tree of order n, Sn a star of order n, and Fm a fan of order 2m + 1, i.e., m triangles sharing exactly one vertex. In this paper, we prove that R(Tn, Fm) = 2n − 1 for n ≥ 3m^2 − 2m − 1, and if Tn = Sn, then the range can be replaced by n ≥ max{m(m − 1) + 1, 6(m − 1)}, which is tight in some sense.",
    keywords = "Tree, Star, Fan, Ramsey number",
    author = "Yanbo Zhang and Broersma, {Haitze J.} and Yaojun Chen",
    year = "2015",
    month = "6",
    doi = "10.1016/j.disc.2015.01.030",
    language = "Undefined",
    volume = "338",
    pages = "994--999",
    journal = "Discrete mathematics",
    issn = "0012-365X",
    publisher = "Elsevier",
    number = "6",

    }

    Ramsey numbers of trees versus fans. / Zhang, Yanbo; Broersma, Haitze J.; Chen, Yaojun.

    In: Discrete mathematics, Vol. 338, No. 6, 06.2015, p. 994-999.

    Research output: Contribution to journalArticleAcademicpeer-review

    TY - JOUR

    T1 - Ramsey numbers of trees versus fans

    AU - Zhang, Yanbo

    AU - Broersma, Haitze J.

    AU - Chen, Yaojun

    PY - 2015/6

    Y1 - 2015/6

    N2 - For two given graphs G1 and G2, the Ramsey number R(G1, G2) is the smallest integerN such that, for any graph G of order N, either G contains G1 as a subgraph or the complement of G contains G2 as a subgraph. Let Tn be a tree of order n, Sn a star of order n, and Fm a fan of order 2m + 1, i.e., m triangles sharing exactly one vertex. In this paper, we prove that R(Tn, Fm) = 2n − 1 for n ≥ 3m^2 − 2m − 1, and if Tn = Sn, then the range can be replaced by n ≥ max{m(m − 1) + 1, 6(m − 1)}, which is tight in some sense.

    AB - For two given graphs G1 and G2, the Ramsey number R(G1, G2) is the smallest integerN such that, for any graph G of order N, either G contains G1 as a subgraph or the complement of G contains G2 as a subgraph. Let Tn be a tree of order n, Sn a star of order n, and Fm a fan of order 2m + 1, i.e., m triangles sharing exactly one vertex. In this paper, we prove that R(Tn, Fm) = 2n − 1 for n ≥ 3m^2 − 2m − 1, and if Tn = Sn, then the range can be replaced by n ≥ max{m(m − 1) + 1, 6(m − 1)}, which is tight in some sense.

    KW - Tree

    KW - Star

    KW - Fan

    KW - Ramsey number

    U2 - 10.1016/j.disc.2015.01.030

    DO - 10.1016/j.disc.2015.01.030

    M3 - Article

    VL - 338

    SP - 994

    EP - 999

    JO - Discrete mathematics

    JF - Discrete mathematics

    SN - 0012-365X

    IS - 6

    ER -