Sharp bounds for decomposing graphs into edges and triangles

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: For a real constant

a l p h a

, let

p i_{3}^{a} l p h a (G)

be the minimum of twice the number of

K_{2}

's plus

a l p h a

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

p i_{3}^{a} l p h a (n)

be the maximum of

p i_{3}^{a} l p h a (G)

over all graphs

G

with

n

vertices. The extremal function

p i_{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, 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

p i_{3}^{3} (n) l e (1 / 2 + o (1)) n^{2}

. We extend their result by determining the exact value of

p i_{3}^{a} l p h a (n)

and the set of extremal graphs for all

a l p h a

and sufficiently large

n

. In particular, we show for

a l p h a = 3

that

K_{n}

and the complete bipartite graph

K_{l f l o o r n / 2 f l o o r, l c e i l n / 2 c e i l}

are the only possible extremal examples for large

n

.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Sharp bounds for decomposing graphs into edges and triangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993262)