Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4656834 | Journal of Combinatorial Theory, Series B | 2014 | 8 Pages |
Abstract
Let G be a K4K4-free graph; an edge in its complement is a K4K4-saturating edge if the addition of this edge to G creates a copy of K4K4. Erdős and Tuza conjectured that for any n -vertex K4K4-free graph G with ⌊n2/4⌋+1⌊n2/4⌋+1 edges, one can find at least (1+o(1))n216K4K4-saturating edges. We construct a graph with only 2n233K4K4-saturating edges. Furthermore, we prove that it is best possible, i.e., one can always find at least (1+o(1))2n233K4K4-saturating edges in an n -vertex K4K4-free graph with ⌊n2/4⌋+1⌊n2/4⌋+1 edges.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
József Balogh, Hong Liu,