Geodesic
Turán number of two vertex-disjoint copies of cliques
Czechoslovak Mathematical Journal, Tome 74 (2024) no. 3, pp. 759-769
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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$.
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$.
DOI : 10.21136/CMJ.2024.0461-23
Classification : 05C35, 05D05
Keywords: clique; Hajnal and Szemerédi theorem; Turán number; extremal graph 
@article{10_21136_CMJ_2024_0461_23,
     author = {Hu, Caiyun},
     title = {Tur\'an number of two vertex-disjoint copies of cliques},
     journal = {Czechoslovak Mathematical Journal},
     pages = {759--769},
     year = {2024},
     volume = {74},
     number = {3},
     doi = {10.21136/CMJ.2024.0461-23},
     mrnumber = {4804958},
     zbl = {07953676},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2024.0461-23/}
}
TY  - JOUR
AU  - Hu, Caiyun
TI  - Turán number of two vertex-disjoint copies of cliques
JO  - Czechoslovak Mathematical Journal
PY  - 2024
SP  - 759
EP  - 769
VL  - 74
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2024.0461-23/
DO  - 10.21136/CMJ.2024.0461-23
LA  - en
ID  - 10_21136_CMJ_2024_0461_23
ER  - 
%0 Journal Article
%A Hu, Caiyun
%T Turán number of two vertex-disjoint copies of cliques
%J Czechoslovak Mathematical Journal
%D 2024
%P 759-769
%V 74
%N 3
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2024.0461-23/
%R 10.21136/CMJ.2024.0461-23
%G en
%F 10_21136_CMJ_2024_0461_23
Hu, Caiyun. Turán number of two vertex-disjoint copies of cliques. Czechoslovak Mathematical Journal, Tome 74 (2024) no. 3, pp. 759-769. doi: 10.21136/CMJ.2024.0461-23

[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 | MR | JFM

[2] Bielak, H., Kieliszek, S.: The Turán number of the graph $2P_5$. Discuss. Math., Graph Theory 36 (2016), 683-694. | DOI | MR | JFM

[3] Brown, W. G., Erdős, P., Simonovits, M.: Extremal problems for directed graphs. J. Comb. Theory, Ser. B 15 (1973), 77-93. | DOI | MR | JFM

[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 | MR | JFM

[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 | MR | JFM

[6] Erdős, P.: Über ein Extremalproblem in der Graphentheorie. Arch. Math. 13 (1962), 222-227 German. | DOI | MR | JFM

[7] Erdős, P., Gallai, T.: On maximal paths and circuits of graphs. Acta Math. Acad. Sci. Hung. 10 (1959), 337-356. | DOI | MR | JFM

[8] Erdős, P., Simonovits, M.: A limit theorem in graph theory. Stud. Sci. Math. Hung. 1 (1966), 51-57. | MR | JFM

[9] Erdős, P., Stone, A. H.: On the structure of linear graphs. Bull. Am. Math. Soc. 52 (1946), 1087-1091. | DOI | MR | JFM

[10] Füredi, Z., Gunderson, D. S.: Extremal numbers for odd cycles. Comb. Probab. Comput. 24 (2015), 641-645. | DOI | MR | JFM

[11] Gorgol, I.: Turán numbers for disjoint copies of graphs. Graphs Comb. 27 (2011), 661-667. | DOI | MR | JFM

[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 | MR | JFM

[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 | JFM

[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 , 12 pages. | arXiv | DOI

[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 , 37 pages. | arXiv | DOI

[16] Hou, J., Li, H., Liu, X., Yuan, L.-T., Zhang, Y.: A step towards a general density Corrádi-Hajnal theorem. Available at , 33 pages. | arXiv | DOI

[17] Liu, H.: Extremal graphs for blow-ups of cycles and trees. Electron. J. Comb. 20 (2013), Article ID P65, 16 pages. | DOI | MR | JFM

[18] Moon, J. W.: On independent complete subgraphs in a graph. Can. J. Math. 20 (1968), 95-102. | DOI | MR | JFM

[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 | JFM

[20] Turán, P.: On an extremal problem in graph theory. Mat. Fiz. Lapok 48 (1941), 436-452 Hungarian. | MR | JFM

[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 | MR | JFM

[22] Yuan, L.-T.: Extremal graphs for the $k$-flower. J. Graph Theory 89 (2018), 26-39. | DOI | MR | JFM

[23] Yuan, L.-T.: Extremal graphs for odd wheels. J. Graph Theory 98 (2021), 691-707. | DOI | MR | JFM

[24] Yuan, L.-T.: Extremal graphs for edge blow-up of graphs. J. Comb. Theory, Ser. B 152 (2022), 379-398. | DOI | MR | JFM

[25] Yuan, L.-T.: Extremal graphs of the $p$th power of paths. Eur. J. Comb. 104 (2022), Article ID 103548, 12 pages. | DOI | MR | JFM

[26] Yuan, L.-T., Zhang, X.-D.: The Turán number of disjoint copies of paths. Discrete Math. 340 (2017), 132-139. | DOI | MR | JFM

[27] Yuan, L.-T., Zhang, X.-D.: Turán numbers for disjoint paths. J. Graph Theory 98 (2021), 499-524. | DOI | MR | JFM

Cité par Sources :