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

Caiyun Hu

Czechoslovak Mathematical Journal (2024)

  • Volume: 74, Issue: 3, page 759-769
  • ISSN: 0011-4642

Abstract

top
The Turán number of a given graph H , denoted by 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 ex ( n , K p ∪ K q ) of a vertex-disjoint union of cliques K p and K q for all values of n .

How to cite

top

Hu, Caiyun. "Turán number of two vertex-disjoint copies of cliques." Czechoslovak Mathematical Journal 74.3 (2024): 759-769. <http://eudml.org/doc/299314>.

@article{Hu2024,
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$.},
author = {Hu, Caiyun},
journal = {Czechoslovak Mathematical Journal},
keywords = {clique; Hajnal and Szemerédi theorem; Turán number; extremal graph},
language = {eng},
number = {3},
pages = {759-769},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Turán number of two vertex-disjoint copies of cliques},
url = {http://eudml.org/doc/299314},
volume = {74},
year = {2024},
}

TY - JOUR
AU - Hu, Caiyun
TI - Turán number of two vertex-disjoint copies of cliques
JO - Czechoslovak Mathematical Journal
PY - 2024
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 74
IS - 3
SP - 759
EP - 769
AB - 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$.
LA - eng
KW - clique; Hajnal and Szemerédi theorem; Turán number; extremal graph
UR - http://eudml.org/doc/299314
ER -

References

top
  1. Bielak, H., Kieliszek, S., 10.2478/umcsmath-2014-0003, Ann. Univ. Mariae Curie-Skłodowska, Sect. A 68 (2014), 21-29. (2014) Zbl1292.05143MR3252513DOI10.2478/umcsmath-2014-0003
  2. Bielak, H., Kieliszek, S., 10.7151/dmgt.1883, Discuss. Math., Graph Theory 36 (2016), 683-694. (2016) Zbl1339.05195MR3518133DOI10.7151/dmgt.1883
  3. Brown, W. G., Erdős, P., Simonovits, M., 10.1016/0095-8956(73)90034-8, J. Comb. Theory, Ser. B 15 (1973), 77-93. (1973) Zbl0253.05124MR0387106DOI10.1016/0095-8956(73)90034-8
  4. Chen, W., Lu, C., Yuan, L.-T., 10.1007/s00373-022-02467-1, Graphs Comb. 38 (2022), Article ID 67, 5 pages. (2022) Zbl1485.05082MR4393992DOI10.1007/s00373-022-02467-1
  5. Silva, J. De, Heysse, K., Kapilow, A., Schenfisch, A., Young, M., 10.1016/j.disc.2017.09.016, Discrete Math. 341 (2018), 492-496. (2018) Zbl1376.05072MR3724116DOI10.1016/j.disc.2017.09.016
  6. Erdős, P., 10.1007/BF01650069, Arch. Math. 13 (1962), 222-227 German. (1962) Zbl0105.17504MR139542DOI10.1007/BF01650069
  7. Erdős, P., Gallai, T., 10.1007/BF02024498, Acta Math. Acad. Sci. Hung. 10 (1959), 337-356. (1959) Zbl0090.39401MR114772DOI10.1007/BF02024498
  8. Erdős, P., Simonovits, M., A limit theorem in graph theory, Stud. Sci. Math. Hung. 1 (1966), 51-57. (1966) Zbl0178.27301MR205876
  9. Erdős, P., Stone, A. H., 10.1090/S0002-9904-1946-08715-7, Bull. Am. Math. Soc. 52 (1946), 1087-1091. (1946) Zbl0063.01277MR0018807DOI10.1090/S0002-9904-1946-08715-7
  10. Füredi, Z., Gunderson, D. S., 10.1017/S0963548314000601, Comb. Probab. Comput. 24 (2015), 641-645. (2015) Zbl1371.05142MR3350026DOI10.1017/S0963548314000601
  11. Gorgol, I., 10.1007/s00373-010-0999-5, Graphs Comb. 27 (2011), 661-667. (2011) Zbl1234.05129MR2824986DOI10.1007/s00373-010-0999-5
  12. Gu, R., Li, X.-L., Shi, Y.-T., 10.1007/s10255-022-1056-x, Acta Math. Appl. Sin., Engl. Ser. 38 (2022), 229-234. (2022) Zbl1484.05103MR4375786DOI10.1007/s10255-022-1056-x
  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. (1970) Zbl0217.02601MR297607
  14. Hou, J., Hu, C., Li, H., Liu, X., Yang, C., Zhang, Y., 10.48550/arXiv.2311.16189, Available at https://arxiv.org/abs/2311.16189 (2023), 12 pages. (2023) DOI10.48550/arXiv.2311.16189
  15. Hou, J., Hu, C., Li, H., Liu, X., Yang, C., Zhang, Y., 10.48550/arXiv.2311.15172, Available at https://arxiv.org/abs/2311.15172 (2023), 37 pages. (2023) DOI10.48550/arXiv.2311.15172
  16. Hou, J., Li, H., Liu, X., Yuan, L.-T., Zhang, Y., 10.48550/arXiv.2302.09849, Available at https://arxiv.org/abs/2302.09849 (2023), 33 pages. (2023) DOI10.48550/arXiv.2302.09849
  17. Liu, H., 10.37236/2856, Electron. J. Comb. 20 (2013), Article ID P65, 16 pages. (2013) Zbl1266.05074MR3040627DOI10.37236/2856
  18. Moon, J. W., 10.4153/CJM-1968-012-x, Can. J. Math. 20 (1968), 95-102. (1968) Zbl0153.54201MR219447DOI10.4153/CJM-1968-012-x
  19. Simonovits, M., A method for solving extremal problems in graph theory, stability problems, Theory of Graphs Academic Press, New York (1968), 279-319. (1968) Zbl0164.24604MR0233735
  20. Turán, P., On an extremal problem in graph theory, Mat. Fiz. Lapok 48 (1941), 436-452 Hungarian. (1941) Zbl0026.26903MR0018405
  21. Xiao, C., Zamora, O., 10.1016/j.disc.2021.112570, Discrete Math. 344 (2021), Article ID 112570, 7 pages. (2021) Zbl1472.05077MR4302081DOI10.1016/j.disc.2021.112570
  22. Yuan, L.-T., 10.1002/jgt.22237, J. Graph Theory 89 (2018), 26-39. (2018) Zbl1432.05057MR3828126DOI10.1002/jgt.22237
  23. Yuan, L.-T., 10.1002/jgt.22727, J. Graph Theory 98 (2021), 691-707. (2021) Zbl1522.05233MR4371474DOI10.1002/jgt.22727
  24. Yuan, L.-T., 10.1016/j.jctb.2021.10.006, J. Comb. Theory, Ser. B 152 (2022), 379-398. (2022) Zbl1478.05083MR4332746DOI10.1016/j.jctb.2021.10.006
  25. Yuan, L.-T., 10.1016/j.ejc.2022.103548, Eur. J. Comb. 104 (2022), Article ID 103548, 12 pages. (2022) Zbl1526.05076MR4414807DOI10.1016/j.ejc.2022.103548
  26. Yuan, L.-T., Zhang, X.-D., 10.1016/j.disc.2016.08.004, Discrete Math. 340 (2017), 132-139. (2017) Zbl1351.05122MR3578809DOI10.1016/j.disc.2016.08.004
  27. Yuan, L.-T., Zhang, X.-D., 10.1002/jgt.22710, J. Graph Theory 98 (2021), 499-524. (2021) Zbl1522.05219MR4371462DOI10.1002/jgt.22710

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.