Ramsey numbers of trees versus fans

Yanbo Zhang, Haitze J. Broersma, Yaojun Chen

    Research output: Contribution to journalArticleAcademicpeer-review

    2 Citations (Scopus)
    29 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