Name
Abstract | ||
|---|---|---|
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 Gy\H{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, Kr\'al', Lidick\'y, 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/2\rfloor,\lceil n/2\rceil}$ are the only possible extremal examples for large $n$. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1017/S0963548320000358 | ACTA MATHEMATICA UNIVERSITATIS COMENIANAE |
DocType | Volume | Issue |
Journal | 88 | 3 |
ISSN | Citations | PageRank |
0231-6986 | 0 | 0.34 |
References | Authors | |
0 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Blumenthal Adam | 1 | 0 | 0.34 |
| Bernard Lidický | 2 | 9 | 5.00 |
| Oleg Pikhurko | 3 | 318 | 47.03 |
| Pehova Yanitsa | 4 | 0 | 0.68 |
| Florian Pfender | 5 | 285 | 30.96 |
| Jan Volec | 6 | 40 | 8.27 |