Czechoslovak Mathematical Journal

Czechoslovak Mathematical Journal, Vol. 74, No. 3, pp. 759-769, 2024

Turán number of two vertex-disjoint copies of cliques

Caiyun Hu

Received October 16, 2023. Published online June 17, 2024.

Abstract: 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$.

Keywords: clique; Hajnal and Szemerédi theorem; Turán number; extremal graph

Classification MSC: 05C35, 05D05

DOI: 10.21136/CMJ.2024.0461-23

PDF available at: Springer Institute of Mathematics CAS Digital Mathematics Library

References:
[1] H. Bielak, S. Kieliszek: The Turán number of the graph $3P_4$. Ann. Univ. Mariae Curie-Skłodowska, Sect. A 68 (2014), 21-29. DOI 10.2478/umcsmath-2014-0003 | MR 3252513 | Zbl 1292.05143
[2] H. Bielak, S. Kieliszek: The Turán number of the graph $2P_5$. Discuss. Math., Graph Theory 36 (2016), 683-694. DOI 10.7151/dmgt.1883 | MR 3518133 | Zbl 1339.05195
[3] W. G. Brown, P. Erdős, M. Simonovits: Extremal problems for directed graphs. J. Comb. Theory, Ser. B 15 (1973), 77-93. DOI 10.1016/0095-8956(73)90034-8 | MR 0387106 | Zbl 0253.05124
[4] W. Chen, C. Lu, L.-T. Yuan: Extremal graphs for two vertex-disjoint copies of a clique. Graphs Comb. 38 (2022), Article ID 67, 5 pages. DOI 10.1007/s00373-022-02467-1 | MR 4393992 | Zbl 1485.05082
[5] J. De Silva, K. Heysse, A. Kapilow, A. Schenfisch, M. Young: Turán numbers of vertex-disjoint cliques in $r$-partite graphs. Discrete Math. 341 (2018), 492-496. DOI 10.1016/j.disc.2017.09.016 | MR 3724116 | Zbl 1376.05072
[6] P. Erdős: Über ein Extremalproblem in der Graphentheorie. Arch. Math. 13 (1962), 222-227. (In German.) DOI 10.1007/BF01650069 | MR 139542 | Zbl 0105.17504
[7] P. Erdős, T. Gallai: On maximal paths and circuits of graphs. Acta Math. Acad. Sci. Hung. 10 (1959), 337-356. DOI 10.1007/BF02024498 | MR 114772 | Zbl 0090.39401
[8] P. Erdős, M. Simonovits: A limit theorem in graph theory. Stud. Sci. Math. Hung. 1 (1966), 51-57. MR 205876 | Zbl 0178.27301
[9] P. Erdős, A. H. Stone: On the structure of linear graphs. Bull. Am. Math. Soc. 52 (1946), 1087-1091. DOI 10.1090/S0002-9904-1946-08715-7 | MR 0018807 | Zbl 0063.01277
[10] Z. Füredi, D. S. Gunderson: Extremal numbers for odd cycles. Comb. Probab. Comput. 24 (2015), 641-645. DOI 10.1017/S0963548314000601 | MR 3350026 | Zbl 1371.05142
[11] I. Gorgol: Turán numbers for disjoint copies of graphs. Graphs Comb. 27 (2011), 661-667. DOI 10.1007/s00373-010-0999-5 | MR 2824986 | Zbl 1234.05129
[12] R. Gu, X.-L. Li, Y.-T. Shi: Hypergraph Turán numbers of vertex disjoint cycles. Acta Math. Appl. Sin., Engl. Ser. 38 (2022), 229-234. DOI 10.1007/s10255-022-1056-x | MR 4375786 | Zbl 1484.05103
[13] A. Hajnal, E. Szemerédi: 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. MR 297607 | Zbl 0217.02601
[14] J. Hou, C. Hu, H. Li, X. Liu, C. Yang, Y. Zhang: Many vertex-disjoint even cycles of fixed length in a graph. Available at https://arxiv.org/abs/2311.16189 (2023), 12 pages. DOI 10.48550/arXiv.2311.16189
[15] J. Hou, C. Hu, H. Li, X. Liu, C. Yang, Y. Zhang: Toward a density Corrádi-Hajnal theorem for degenerate hypergraphs. Available at https://arxiv.org/abs/2311.15172 (2023), 37 pages. DOI 10.48550/arXiv.2311.15172
[16] J. Hou, H. Li, X. Liu, L.-T. Yuan, Y. Zhang: A step towards a general density Corrádi-Hajnal theorem. Available at https://arxiv.org/abs/2302.09849 (2023), 33 pages. DOI 10.48550/arXiv.2302.09849
[17] H. Liu: Extremal graphs for blow-ups of cycles and trees. Electron. J. Comb. 20 (2013), Article ID P65, 16 pages. DOI 10.37236/2856 | MR 3040627 | Zbl 1266.05074
[18] J. W. Moon: On independent complete subgraphs in a graph. Can. J. Math. 20 (1968), 95-102. DOI 10.4153/CJM-1968-012-x | MR 219447 | Zbl 0153.54201
[19] M. Simonovits: A method for solving extremal problems in graph theory, stability problems. Theory of Graphs. Academic Press, New York (1968), 279-319. MR 0233735 | Zbl 0164.24604
[20] P. Turán: On an extremal problem in graph theory. Mat. Fiz. Lapok 48 (1941), 436-452. (In Hungarian.) MR 0018405 | Zbl 0026.26903
[21] C. Xiao, O. Zamora: A note on the Turán number of disjoint union of wheels. Discrete Math. 344 (2021), Article ID 112570, 7 pages. DOI 10.1016/j.disc.2021.112570 | MR 4302081 | Zbl 1472.05077
[22] L.-T. Yuan: Extremal graphs for the $k$-flower. J. Graph Theory 89 (2018), 26-39. DOI 10.1002/jgt.22237 | MR 3828126 | Zbl 1432.05057
[23] L.-T. Yuan: Extremal graphs for odd wheels. J. Graph Theory 98 (2021), 691-707. DOI 10.1002/jgt.22727 | MR 4371474 | Zbl 1522.05233
[24] L.-T. Yuan: Extremal graphs for edge blow-up of graphs. J. Comb. Theory, Ser. B 152 (2022), 379-398. DOI 10.1016/j.jctb.2021.10.006 | MR 4332746 | Zbl 1478.05083
[25] L.-T. Yuan: Extremal graphs of the $p$th power of paths. Eur. J. Comb. 104 (2022), Article ID 103548, 12 pages. DOI 10.1016/j.ejc.2022.103548 | MR 4414807 | Zbl 1526.05076
[26] L.-T. Yuan, X.-D. Zhang: The Turán number of disjoint copies of paths. Discrete Math. 340 (2017), 132-139. DOI 10.1016/j.disc.2016.08.004 | MR 3578809 | Zbl 1351.05122
[27] L.-T. Yuan, X.-D. Zhang: Turán numbers for disjoint paths. J. Graph Theory 98 (2021), 499-524. DOI 10.1002/jgt.22710 | MR 4371462 | Zbl 1522.05219

Affiliations: Caiyun Hu, Fuzhou University, Qishan Campus, Shangjiezhen, Minhou County, Fuzhou, 350108 P. R. China, e-mail: hucaiyun.fzu@gmail.com

Springer subscribers can access the papers on Springer website.

[List of online first articles] [Contents of Czechoslovak Mathematical Journal] [Full text of the older issues of Czechoslovak Mathematical Journal at DML-CZ]

PDF available at:

Springer
for subscribers

···

Institute of Mathematics CAS
fulltext not available (moving wall 24 months)

···

Digital Mathematics Library
fulltext not available (moving wall 24 months)