1. bookVolume 38 (2018): Issue 3 (August 2018)
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Turán Function and H-Decomposition Problem for Gem Graphs

Published Online: 19 Jun 2018
Volume & Issue: Volume 38 (2018) - Issue 3 (August 2018)
Page range: 717 - 741
Received: 10 Oct 2016
Accepted: 02 Feb 2017
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
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 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.

Keywords

MSC 2010

[1] P. Allen, J. Böttcher and Y. Person, An improved error term for minimum H- decompositions of graphs, J. Combin. Theory Ser. B 108 (2014) 92–101. doi:10.1016/j.jctb.2014.03.00110.1016/j.jctb.2014.03.001Search in Google Scholar

[2] B. Bollobás, On complete subgraphs of different orders, Math. Proc. Cambridge Philos. Soc. 79 (1976) 19–24. doi:10.1017/S030500410005206310.1017/S0305004100052063Search in Google Scholar

[3] D. Dor and M. Tarsi, Graph decomposition is NP-complete: a complete proof of Holyer’s conjecture, SIAM J. Comput. 26 (1997) 1166–1187. doi:10.1137/S009753979222950710.1137/S0097539792229507Search in Google Scholar

[4] P. Erdős, A.W. Goodman and L. Pósa, The representation of a graph by set intersections, Canad. J. Math. 18 (1966) 106–112. doi:10.4153/CJM-1966-014-310.4153/CJM-1966-014-3Search in Google Scholar

[5] R. Faudree and R. Schelp, Path Ramsey numbers in multicolorings, J. Combin. Theory Ser. B 19 (1975) 150–160. doi:10.1016/0095-8956(75)90080-510.1016/0095-8956(75)90080-5Search in Google Scholar

[6] H. Liu and T. Sousa, Decompositions of graphs into fans and single edges, J. Graph Theory 85 (2017) 400–411. doi:/10.1002/jgt.2206910.1002/jgt.22069Search in Google Scholar

[7] L. Özkahya and Y. Person, Minimum H-decompositions of graphs: edge-critical case, J. Combin. Theory Ser. B 102 (2012) 715–725. doi:10.1016/j.jctb.2011.10.00410.1016/j.jctb.2011.10.004Search in Google Scholar

[8] O. Pikhurko, A note on the Turán function of even cycles, Proc. Amer. Math. Soc. 140 (2012) 3687–3692. doi:10.1090/S0002-9939-2012-11274-210.1090/S0002-9939-2012-11274-2Search in Google Scholar

[9] O. Pikhurko and T. Sousa, Minimum H-decompositions of graphs, J. Combin. Theory Ser. B 97 (2007) 1041–1055. doi:10.1016/j.jctb.2007.03.00210.1016/j.jctb.2007.03.002Search in Google Scholar

[10] T. Sousa, Decompositions of graphs into 5-cycles and other small graphs, Electron. J. Combin. 12 (2005) #R49.10.37236/1946Search in Google Scholar

[11] T. Sousa, Decompositions of graphs into a given clique-extension, Ars Combin. 100 (2011) 465–472.Search in Google Scholar

[12] T. Sousa, Decompositions of graphs into cycles of length seven and single edges, Ars Combin. 119 (2015) 321–329.Search in Google Scholar

[13] P. Turán, On an extremal problem in graph theory, Mat. Fiz. Lapok 48 (1941) 436–452.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo