Article
| Title: | Turán number of two vertex-disjoint copies of cliques (English) |
| Author: | Hu, Caiyun |
| Language: | English |
| Journal: | Czechoslovak Mathematical Journal |
| ISSN: | 0011-4642 (print) |
| ISSN: | 1572-9141 (online) |
| Volume: | 74 |
| Issue: | 3 |
| Year: | 2024 |
| Pages: | 759-769 |
| Summary lang: | English |
| . | |
| Category: | math |
| . | |
| Summary: | The Turán number of a given graph $H$, denoted by ${\rm ex}(n,H)$, is the maximum number of edges in an $H$-free graph on $n$ vertices. Applying a well-known result of Hajnal and Szemerédi, we determine the Turán number $\text {ex}(n, K_p \cup K_q$) of a vertex-disjoint union of cliques $K_p$ and $K_q$ for all values of $n$. (English) |
| Keyword: | clique |
| Keyword: | Hajnal and Szemerédi theorem |
| Keyword: | Turán number |
| Keyword: | extremal graph |
| MSC: | 05C35 |
| MSC: | 05D05 |
| DOI: | 10.21136/CMJ.2024.0461-23 |
| . | |
| Date available: | 2024-10-03T12:35:46Z |
| Last updated: | 2024-10-04 |
| Stable URL: | http://hdl.handle.net/10338.dmlcz/152579 |
| . | |
| Reference: | [1] Bielak, H., Kieliszek, S.: The Turán number of the graph $3P_4$.Ann. Univ. Mariae Curie-Skłodowska, Sect. A 68 (2014), 21-29. Zbl 1292.05143, MR 3252513, 10.2478/umcsmath-2014-0003 |
| Reference: | [2] Bielak, H., Kieliszek, S.: The Turán number of the graph $2P_5$.Discuss. Math., Graph Theory 36 (2016), 683-694. Zbl 1339.05195, MR 3518133, 10.7151/dmgt.1883 |
| Reference: | [3] Brown, W. G., Erdős, P., Simonovits, M.: Extremal problems for directed graphs.J. Comb. Theory, Ser. B 15 (1973), 77-93. Zbl 0253.05124, MR 0387106, 10.1016/0095-8956(73)90034-8 |
| Reference: | [4] Chen, W., Lu, C., Yuan, L.-T.: Extremal graphs for two vertex-disjoint copies of a clique.Graphs Comb. 38 (2022), Article ID 67, 5 pages. Zbl 1485.05082, MR 4393992, 10.1007/s00373-022-02467-1 |
| Reference: | [5] Silva, J. De, Heysse, K., Kapilow, A., Schenfisch, A., Young, M.: Turán numbers of vertex-disjoint cliques in $r$-partite graphs.Discrete Math. 341 (2018), 492-496. Zbl 1376.05072, MR 3724116, 10.1016/j.disc.2017.09.016 |
| Reference: | [6] Erdős, P.: Über ein Extremalproblem in der Graphentheorie.Arch. Math. 13 (1962), 222-227 German. Zbl 0105.17504, MR 139542, 10.1007/BF01650069 |
| Reference: | [7] Erdős, P., Gallai, T.: On maximal paths and circuits of graphs.Acta Math. Acad. Sci. Hung. 10 (1959), 337-356. Zbl 0090.39401, MR 114772, 10.1007/BF02024498 |
| Reference: | [8] Erdős, P., Simonovits, M.: A limit theorem in graph theory.Stud. Sci. Math. Hung. 1 (1966), 51-57. Zbl 0178.27301, MR 205876 |
| Reference: | [9] Erdős, P., Stone, A. H.: On the structure of linear graphs.Bull. Am. Math. Soc. 52 (1946), 1087-1091. Zbl 0063.01277, MR 0018807, 10.1090/S0002-9904-1946-08715-7 |
| Reference: | [10] Füredi, Z., Gunderson, D. S.: Extremal numbers for odd cycles.Comb. Probab. Comput. 24 (2015), 641-645. Zbl 1371.05142, MR 3350026, 10.1017/S0963548314000601 |
| Reference: | [11] Gorgol, I.: Turán numbers for disjoint copies of graphs.Graphs Comb. 27 (2011), 661-667. Zbl 1234.05129, MR 2824986, 10.1007/s00373-010-0999-5 |
| Reference: | [12] Gu, R., Li, X.-L., Shi, Y.-T.: Hypergraph Turán numbers of vertex disjoint cycles.Acta Math. Appl. Sin., Engl. Ser. 38 (2022), 229-234. Zbl 1484.05103, MR 4375786, 10.1007/s10255-022-1056-x |
| Reference: | [13] Hajnal, A., Szemerédi, E.: Proof of a conjecture of P. Erdős.Combinatorial Theory and Its Applications, I-III Colloquia Mathematica Societatis János Bolyai 4. North-Holland, Amsterdam (1970), 601-623. Zbl 0217.02601, MR 297607 |
| Reference: | [14] Hou, J., Hu, C., Li, H., Liu, X., Yang, C., Zhang, Y.: Many vertex-disjoint even cycles of fixed length in a graph.Available at https://arxiv.org/abs/2311.16189 (2023), 12 pages. 10.48550/arXiv.2311.16189 |
| Reference: | [15] Hou, J., Hu, C., Li, H., Liu, X., Yang, C., Zhang, Y.: Toward a density Corrádi-Hajnal theorem for degenerate hypergraphs.Available at https://arxiv.org/abs/2311.15172 (2023), 37 pages. 10.48550/arXiv.2311.15172 |
| Reference: | [16] Hou, J., Li, H., Liu, X., Yuan, L.-T., Zhang, Y.: A step towards a general density Corrádi-Hajnal theorem.Available at https://arxiv.org/abs/2302.09849 (2023), 33 pages. 10.48550/arXiv.2302.09849 |
| Reference: | [17] Liu, H.: Extremal graphs for blow-ups of cycles and trees.Electron. J. Comb. 20 (2013), Article ID P65, 16 pages. Zbl 1266.05074, MR 3040627, 10.37236/2856 |
| Reference: | [18] Moon, J. W.: On independent complete subgraphs in a graph.Can. J. Math. 20 (1968), 95-102. Zbl 0153.54201, MR 219447, 10.4153/CJM-1968-012-x |
| Reference: | [19] Simonovits, M.: A method for solving extremal problems in graph theory, stability problems.Theory of Graphs Academic Press, New York (1968), 279-319. Zbl 0164.24604, MR 0233735 |
| Reference: | [20] Turán, P.: On an extremal problem in graph theory.Mat. Fiz. Lapok 48 (1941), 436-452 Hungarian. Zbl 0026.26903, MR 0018405 |
| Reference: | [21] Xiao, C., Zamora, O.: A note on the Turán number of disjoint union of wheels.Discrete Math. 344 (2021), Article ID 112570, 7 pages. Zbl 1472.05077, MR 4302081, 10.1016/j.disc.2021.112570 |
| Reference: | [22] Yuan, L.-T.: Extremal graphs for the $k$-flower.J. Graph Theory 89 (2018), 26-39. Zbl 1432.05057, MR 3828126, 10.1002/jgt.22237 |
| Reference: | [23] Yuan, L.-T.: Extremal graphs for odd wheels.J. Graph Theory 98 (2021), 691-707. Zbl 1522.05233, MR 4371474, 10.1002/jgt.22727 |
| Reference: | [24] Yuan, L.-T.: Extremal graphs for edge blow-up of graphs.J. Comb. Theory, Ser. B 152 (2022), 379-398. Zbl 1478.05083, MR 4332746, 10.1016/j.jctb.2021.10.006 |
| Reference: | [25] Yuan, L.-T.: Extremal graphs of the $p$th power of paths.Eur. J. Comb. 104 (2022), Article ID 103548, 12 pages. Zbl 1526.05076, MR 4414807, 10.1016/j.ejc.2022.103548 |
| Reference: | [26] Yuan, L.-T., Zhang, X.-D.: The Turán number of disjoint copies of paths.Discrete Math. 340 (2017), 132-139. Zbl 1351.05122, MR 3578809, 10.1016/j.disc.2016.08.004 |
| Reference: | [27] Yuan, L.-T., Zhang, X.-D.: Turán numbers for disjoint paths.J. Graph Theory 98 (2021), 499-524. Zbl 1522.05219, MR 4371462, 10.1002/jgt.22710 |
| . |
Fulltext not available (moving wall 24 months)
Search
Partner of
