On the number of K₄-saturating edges

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}

. ErdH{o}s and Tuza conjectured that for any

n

-vertex

K_{4}

-free graph

G

with

l f l o o r n^{2} / 4 f l o o r + 1

edges, one can find at least

(1 + o (1)) f r a c n^{2} 16

K_{4}

-saturating edges. We construct a graph with only

f r a c 2 n^{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)) f r a c 2 n^{2} 33

K_{4}

-saturating edges in an

n

-vertex

K_{4}

-free graph with

l f l o o r n^{2} / 4 f l o o r + 1

edges.

Recommendations

Cites Work

Cited In (5)

This page was built for publication: On the number of \(K_4\)-saturating edges