Authors: H. Liu, T. Sousa Title: Turán function and H-decomposition problem for gem graphs Source: Discussiones Mathematicae Graph Theory Received 10.10.2016, Revised 26.01.2017, Accepted 02.02.2017, doi: 10.7151/dmgt.2046 | |
Abstract: 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 gem_{4} and gem_{5}. The graph gem_{4} consists of the path P_{4} 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 gem_{5} is similarly defined with the path P_{5} on five vertices. We determine the Turán functions ex(n,gem_{4}) and ex(n,gem_{5}), and verify the conjecture of Pikhurko and Sousa when H is the graph gem_{4} and gem_{5}. | |
Keywords: gem graph, Turán function, extremal graph, graph decomposition | |
Links: |