Article
Full entry | Fulltext not available
(moving wall
24 months)
Feedback
Keywords:
clique; Hajnal and Szemerédi theorem; Turán number; extremal graph
clique; Hajnal and Szemerédi theorem; Turán number; extremal graph
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$.
References:
[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. DOI 10.2478/umcsmath-2014-0003 | MR 3252513 | Zbl 1292.05143
[2] Bielak, H., Kieliszek, S.: 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] Brown, W. G., Erdős, P., Simonovits, M.: 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] 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. DOI 10.1007/s00373-022-02467-1 | MR 4393992 | Zbl 1485.05082
[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. DOI 10.1016/j.disc.2017.09.016 | MR 3724116 | Zbl 1376.05072
[6] Erdős, P.: Über ein Extremalproblem in der Graphentheorie. Arch. Math. 13 (1962), 222-227 German. DOI 10.1007/BF01650069 | MR 139542 | Zbl 0105.17504
[7] Erdős, P., Gallai, T.: 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] Erdős, P., Simonovits, M.: A limit theorem in graph theory. Stud. Sci. Math. Hung. 1 (1966), 51-57. MR 205876 | Zbl 0178.27301
[9] Erdős, P., Stone, A. H.: 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] Füredi, Z., Gunderson, D. S.: Extremal numbers for odd cycles. Comb. Probab. Comput. 24 (2015), 641-645. DOI 10.1017/S0963548314000601 | MR 3350026 | Zbl 1371.05142
[11] Gorgol, I.: 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] 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. DOI 10.1007/s10255-022-1056-x | MR 4375786 | Zbl 1484.05103
[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. MR 297607 | Zbl 0217.02601
[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. DOI 10.48550/arXiv.2311.16189
[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. DOI 10.48550/arXiv.2311.15172
[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. DOI 10.48550/arXiv.2302.09849
[17] Liu, H.: 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] Moon, J. W.: 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] Simonovits, M.: 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] Turán, P.: On an extremal problem in graph theory. Mat. Fiz. Lapok 48 (1941), 436-452 Hungarian. MR 0018405 | Zbl 0026.26903
[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. DOI 10.1016/j.disc.2021.112570 | MR 4302081 | Zbl 1472.05077
[22] Yuan, L.-T.: Extremal graphs for the $k$-flower. J. Graph Theory 89 (2018), 26-39. DOI 10.1002/jgt.22237 | MR 3828126 | Zbl 1432.05057
[23] Yuan, L.-T.: Extremal graphs for odd wheels. J. Graph Theory 98 (2021), 691-707. DOI 10.1002/jgt.22727 | MR 4371474 | Zbl 1522.05233
[24] Yuan, L.-T.: 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] Yuan, L.-T.: 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] Yuan, L.-T., Zhang, X.-D.: 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] Yuan, L.-T., Zhang, X.-D.: Turán numbers for disjoint paths. J. Graph Theory 98 (2021), 499-524. DOI 10.1002/jgt.22710 | MR 4371462 | Zbl 1522.05219
Search
Partner of
