Abstract
Let G be a K4-free graph; an edge in its complement is a K4-saturating edge if the addition of this edge to G creates a copy of K4. Erdos and Tuza conjectured that for any n-vertex K4-free graph G with ⌊n2/4⌋+1 edges, one can find at least (1+o(1))n216 K4-saturating edges. We construct a graph with only 2n233 K4-saturating edges. Furthermore, we prove that it is best possible, i.e., one can always find at least (1+o(1))2n233 K4-saturating edges in an n-vertex K4-free graph with ⌊n2/4⌋+1 edges.
Original language | English (US) |
---|---|
Pages (from-to) | 250-257 |
Number of pages | 8 |
Journal | Journal of Combinatorial Theory. Series B |
Volume | 109 |
DOIs | |
State | Published - Nov 1 2014 |
Keywords
- Erdos-Tuza conjecture
- Extremal number
- Graphs
- K
- Saturating edges
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics