For a real constant $alpha$, let $pi_3^alpha(G)$ be the minimum of twice the number of $K_2$s plus $alpha$ 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 GyH{o}ri and Tuza [Decompositions of graphs into complete subgraphs of given order, Studia Sci. Math. Hungar. 22 (1987), 315--320]. In a recent progress on this problem, Kral, Lidicky, Martins and Pehova [Decomposing graphs into edges and triangles, Combin. Prob. 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 $alpha$ and sufficiently large $n$. In particular, we show for $alpha=3$ that $K_n$ and the complete bipartite graph $K_{lfloor n/2rfloor,lceil n/2rceil}$ are the only possible extremal examples for large $n$.
تحميل البحث