Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9514434 | Discrete Mathematics | 2018 | 11 Pages |
Abstract
Given graphs H1,â¦,Ht, a graph G is (H1,â¦,Ht)-Ramsey-minimal if every t-coloring of the edges of G contains a monochromatic Hi in color i for some iâ{1,â¦,t}, but any proper subgraph of G does not possess this property. We define Rmin(H1,â¦,Ht) to be the family of (H1,â¦,Ht)-Ramsey-minimal graphs. A graph G is Rmin(H1,â¦,Ht)-saturated if no element of Rmin(H1,â¦,Ht) is a subgraph of G, but for any edge e in G¯, some element of Rmin(H1,â¦,Ht) is a subgraph of G+e. We define sat(n,Rmin(H1,â¦,Ht)) to be the minimum number of edges over all Rmin(H1,â¦,Ht)-saturated graphs on n vertices. In 1987, Hanson and Toft conjectured that sat(n,Rmin(Kk1,â¦,Kkt))=(râ2)(nâr+2)+râ22 for nâ¥r, where r=r(Kk1,â¦,Kkt) is the classical Ramsey number for complete graphs. The first non-trivial case of Hanson and Toft's conjecture for sufficiently large n was settled in 2011, and is so far the only settled case. Motivated by Hanson and Toft's conjecture, we study the minimum number of edges over all Rmin(K3,Tk)-saturated graphs on n vertices, where Tk is the family of all trees on k vertices. We show that for nâ¥18, sat(n,Rmin(K3,T4))=â5nâ2â. For kâ¥5 and nâ¥2k+(âkâ2â+1)âkâ2ââ2, we obtain an asymptotic bound for sat(n,Rmin(K3,Tk)) by showing that 32+12k2nâcâ¤sat(n,Rmin(K3,Tk))â¤32+12k2n+C, where c=12k2+32kâ2 and C=2k2â6k+32âk2kâ12k2â1.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Martin Rolek, Zi-Xia Song,