Turán Function and H-Decomposition Problem for Gem Graphs
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 ϕ...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2018-08-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.2046 |
| _version_ | 1827844675556343808 |
|---|---|
| author | Liu Henry Sousa Teresa |
| author_facet | Liu Henry Sousa Teresa |
| author_sort | Liu Henry |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-12T08:45:17Z |
| format | Article |
| id | doaj.art-db9e5c228e424a969d0594d8e2ef41b4 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T08:45:17Z |
| publishDate | 2018-08-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-db9e5c228e424a969d0594d8e2ef41b42023-09-02T16:29:33ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922018-08-0138371774110.7151/dmgt.2046dmgt.2046Turán Function and H-Decomposition Problem for Gem GraphsLiu Henry0Sousa Teresa1School of Mathematics and Statistics, Central South University, Changsha410083, ChinaEscola Naval and Centro de Investigação Naval, Escola Naval - Alfeite, 2810-001Almada, Portugal; Centro de Matemática e Aplicações, Faculdade de Ciências e Tecnologia, Universidade Nova de Lisboa, Campus de Caparica, 2829-516Caparica, PortugalGiven 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.https://doi.org/10.7151/dmgt.2046gem graphturán functionextremal graphgraph decomposition05c3505c70 |
| spellingShingle | Liu Henry Sousa Teresa Turán Function and H-Decomposition Problem for Gem Graphs Discussiones Mathematicae Graph Theory gem graph turán function extremal graph graph decomposition 05c35 05c70 |
| title | Turán Function and H-Decomposition Problem for Gem Graphs |
| title_full | Turán Function and H-Decomposition Problem for Gem Graphs |
| title_fullStr | Turán Function and H-Decomposition Problem for Gem Graphs |
| title_full_unstemmed | Turán Function and H-Decomposition Problem for Gem Graphs |
| title_short | Turán Function and H-Decomposition Problem for Gem Graphs |
| title_sort | turan function and h decomposition problem for gem graphs |
| topic | gem graph turán function extremal graph graph decomposition 05c35 05c70 |
| url | https://doi.org/10.7151/dmgt.2046 |
| work_keys_str_mv | AT liuhenry turanfunctionandhdecompositionproblemforgemgraphs AT sousateresa turanfunctionandhdecompositionproblemforgemgraphs |