TY - JOUR

T1 - Turán function and h-decomposition problem for gem graphs

AU - Liu, Henry

AU - Sousa, Teresa

N1 - info:eu-repo/grantAgreement/FCT/5876/147204/PT#
Henry Liu was supported by the International Interchange Plan of CSU, and the China Postdoctoral Science Foundation (Nos. 2015M580695 and 2016T90756).

PY - 2018

Y1 - 2018

N2 - Given a graph H, the Turán function ex(n, H) is the maximum number of edges in a graph on n vertices not containing H as a subgraph. For two graphs G and H, an H-decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a graph isomorphic to H. Let Φ(n, H) be the smallest number Φ such that any graph G of order n admits an H-decomposition with at most Φ parts. Pikhurko and Sousa conjectured that Φ(n, H) = ex(n, H) for χ(H) ≥ 3 and all sufficiently large n. Their conjecture has been verified by Özkahya and Person for all edge-critical graphs H. In this article, we consider the gem graphs gem4 and gem5. The graph gem4 consists of the path P4 with four vertices a, b, c, d and edges ab, bc, cd plus a universal vertex u adjacent to a, b, c, d, and the graph gem5 is similarly defined with the path P5 on five vertices. We determine the Turán functions ex(n, gem4) and ex(n, gem5), and verify the conjecture of Pikhurko and Sousa when H is the graph gem4 and gem5

AB - Given a graph H, the Turán function ex(n, H) is the maximum number of edges in a graph on n vertices not containing H as a subgraph. For two graphs G and H, an H-decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a graph isomorphic to H. Let Φ(n, H) be the smallest number Φ such that any graph G of order n admits an H-decomposition with at most Φ parts. Pikhurko and Sousa conjectured that Φ(n, H) = ex(n, H) for χ(H) ≥ 3 and all sufficiently large n. Their conjecture has been verified by Özkahya and Person for all edge-critical graphs H. In this article, we consider the gem graphs gem4 and gem5. The graph gem4 consists of the path P4 with four vertices a, b, c, d and edges ab, bc, cd plus a universal vertex u adjacent to a, b, c, d, and the graph gem5 is similarly defined with the path P5 on five vertices. We determine the Turán functions ex(n, gem4) and ex(n, gem5), and verify the conjecture of Pikhurko and Sousa when H is the graph gem4 and gem5

KW - Extremal graph

KW - Gem graph

KW - Graph decomposition.

KW - Turán function

UR - http://www.scopus.com/inward/record.url?scp=85048256890&partnerID=8YFLogxK

U2 - 10.7151/dmgt.2046

DO - 10.7151/dmgt.2046

M3 - Article

AN - SCOPUS:85048256890

SN - 1234-3099

VL - 38

SP - 717

EP - 741

JO - Discussiones Mathematicae Graph Theory

JF - Discussiones Mathematicae Graph Theory

IS - 3

ER -