Saturation Numbers For Ramsey-Minimal Graphs

Keywords

Ramsey-minimal; Saturated graph; Saturation number

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)+[Formula presented] 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 [Formula presented]+[Formula presented]n−c≤sat(n,Rmin(K3,Tk))≤[Formula presented]+[Formula presented]n+C, where c=[Formula presented]+[Formula presented]k−2 and C=2k2−6k+[Formula presented]−[Formula presented]k−[Formula presented]−1.

Publication Date

12-1-2018

Publication Title

Discrete Mathematics

Volume

341

Issue

12

Number of Pages

3310-3320

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/j.disc.2018.08.012

Socpus ID

85053141522 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/85053141522

This document is currently not available here.

Share

COinS