## Abstract

Let G be a K_{4}-free graph; an edge in its complement is a K_{4}-saturating edge if the addition of this edge to G creates a copy of K_{4}. Erdos and Tuza conjectured that for any n-vertex K_{4}-free graph G with ⌊n^{2}/4⌋+1 edges, one can find at least (1+o(1))n216 K_{4}-saturating edges. We construct a graph with only 2n233 K_{4}-saturating edges. Furthermore, we prove that it is best possible, i.e., one can always find at least (1+o(1))2n233 K_{4}-saturating edges in an n-vertex K_{4}-free graph with ⌊n^{2}/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

## Fingerprint

Dive into the research topics of 'On the number of K_{4}-saturating edges'. Together they form a unique fingerprint.