Search for: All records

Abstract For a real constant α , let $$\pi _3^\alpha (G)$$ be the minimum of twice the number of K 2 ’s plus α times the number of K 3 ’s over all edge decompositions of G into copies of K 2 and K 3 , where K r denotes the complete graph on r vertices. Let $$\pi _3^\alpha (n)$$ be the maximum of $$\pi _3^\alpha (G)$$ over all graphs G with n vertices. The extremal function $$\pi _3^3(n)$$ was first studied by Győri and Tuza ( Studia Sci. Math. Hungar. 22 (1987) 315–320). In recent progress on this problem, Král’, Lidický, Martins and Pehova ( Combin. Probab. Comput. 28 (2019) 465–472) proved via flag algebras that $$\pi _3^3(n) \le (1/2 + o(1)){n^2}$$ . We extend their result by determining the exact value of $$\pi _3^\alpha (n)$$ and the set of extremal graphs for all α and sufficiently large n . In particular, we show for α = 3 that K n and the complete bipartite graph $${K_{\lfloor n/2 \rfloor,\lceil n/2 \rceil }}$$ are the only possible extremal examples for large n .