Geodesic
Turán Function and H-Decomposition Problem for Gem Graphs
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 3, pp. 717-741.

Voir la notice de l'article provenant de la source Library of Science

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: gem graph, Turán function, extremal graph, graph decomposition 
@article{DMGT_2018_38_3_a7,
     author = {Liu, Henry and Sousa, Teresa},
     title = {Tur\'an {Function} and {H-Decomposition} {Problem} for {Gem} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {717--741},
     publisher = {mathdoc},
     volume = {38},
     number = {3},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a7/}
}
TY  - JOUR
AU  - Liu, Henry
AU  - Sousa, Teresa
TI  - Turán Function and H-Decomposition Problem for Gem Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 717
EP  - 741
VL  - 38
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a7/
LA  - en
ID  - DMGT_2018_38_3_a7
ER  - 
%0 Journal Article
%A Liu, Henry
%A Sousa, Teresa
%T Turán Function and H-Decomposition Problem for Gem Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 717-741
%V 38
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a7/
%G en
%F DMGT_2018_38_3_a7
Liu, Henry; Sousa, Teresa. Turán Function and H-Decomposition Problem for Gem Graphs. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 3, pp. 717-741. http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a7/

[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.001

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

[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/S0097539792229507

[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-3

[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-5

[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.22069

[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.004

[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-2

[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.002

[10] T. Sousa, Decompositions of graphs into 5 -cycles and other small graphs, Electron. J. Combin. 12 (2005) #R49.

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

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

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