Journal of Combinatorics

Volume 2 (2011)

Saturation numbers for families of Ramsey-minimal graphs

Pages: 435 – 455

DOI: http://dx.doi.org/10.4310/JOC.2011.v2.n3.a5

Authors

Guantao Chen (Georgia State University, Atlanta, Ga., U.S.A.)

Michael Ferrara (University of Colorado, Denver, Colo., U.S.A.)

Ronald J. Gould (Department of Mathematics, Emory University, Atlanta, Ga., U.S.A.)

Colton Magnant (Georgia Southern University, Statesboro, Ga., U.S.A.)

John Schmitt (Middlebury College, Middlebury, Vt., U.S.A.)

Abstract

Given a family of graphs $\F$, a graph $G$ is {\it$\F$-saturated} ifno element of $\F$ is a subgraph of $G$, but for any edge $e$ in$\overline{G}$, some element of $\F$ is a subgraph of $G+e$. Let$sat(n,\F)$ denote the minimum number of edges in an $\F$-saturatedgraph of order $n$.

For graphs $G, H_1,\dots, H_k$, we write that $G\rightarrow(H_1,\dots,H_k)$ if every $k$-coloring of $E(G)$ contains a monochromatic copy of$H_i$ in color $i$ for some $i$. A graph $G$ is {\it$(H_1,\dots,H_k)$-Ramsey-minimal} if $G\rightarrow(H_1,\dots, H_k)$ but for any$e\in G$, $(G-e)\not\rightarrow(H_1,\dots, H_k)$. Let $\Rm(H_1,\dots,H_k)$ denote the family of $(H_1,\dots, H_k)$-Ramsey-minimal graphs.

In 1987, Hanson and Toft conjectured that%\begin{align*}&sat(n,\Rm(K_{k_1}, \dots, K_{k_t}))&\quad{} =%\]%%\[\left\{%\begin{array}{ll}{n \choose2} & n < r[4pt]{r - 2 \choose2} + (r - 2)(n - r + 2) & n\ge r,\end{array}%\right.\end{align*}%where $r = r(k_{1}, k_{2}, \dots, k_{t})$ is the classical Ramseynumber for cliques.

In this paper, we settle the first non-trivial case of Hanson andToft’s conjecture for sufficiently large $n$ by showing that $sat(n,\break\Rm(K_3,K_3))=4n-10$ for $n\ge56$. We also undertake a briefinvestigation of $sat(n,\Rm(K_t,T_m))$ where $T_m$ is a tree of order $m$.

Keywords

Ramsey-minimal, saturation number

2010 Mathematics Subject Classification

05C35, 05C55

Full Text (PDF format)