pith. sign in

arxiv: 1312.5248 · v2 · pith:KWQ3KBUEnew · submitted 2013-12-18 · 🧮 math.CO

On the number of K₄-saturating edges

classification 🧮 math.CO
keywords edgessaturatinggraphedgefracfreefindleast
0
0 comments X
read the original abstract

Let $G$ be a $K_4$-free graph, an edge in its complement is a $K_4$-\emph{saturating} edge if the addition of this edge to $G$ creates a copy of $K_4$. Erd\H{o}s and Tuza conjectured that for any $n$-vertex $K_4$-free graph $G$ with $\lfloor n^2/4\rfloor+1$ edges, one can find at least $(1+o(1))\frac{n^2}{16}$ $K_4$-saturating edges. We construct a graph with only $\frac{2n^2}{33}$ $K_4$-saturating edges. Furthermore, we prove that it is best possible, i.e., one can always find at least $(1+o(1))\frac{2n^2}{33}$ $K_4$-saturating edges in an $n$-vertex $K_4$-free graph with $\lfloor n^2/4\rfloor+1$ edges.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.