×

Extremal graphs for edge blow-up of graphs. (English) Zbl 1478.05083

Summary: Given a graph \(H\) and an integer \(p\), the edge blow-up \(H^{p+1}\) of \(H\) is the graph obtained from replacing each edge in \(H\) by a clique of order \(p+1\) where the new vertices of the cliques are all distinct. The Turán numbers for edge blow-up of matchings were first studied by P. Erdős [Arch. Math. 13, 222–227 (1962; Zbl 0105.17504)] and J. W. Moon [Can. J. Math. 20, 95–102 (1968; Zbl 0153.54201)]. In this paper, we determine the range of the Turán numbers for edge blow-up of all bipartite graphs and the exact Turán numbers for edge blow-up of all non-bipartite graphs. In addition, we characterize the extremal graphs for edge blow-up of all non-bipartite graphs. Our results also extend several known results, including the Turán numbers for edge blow-up of stars, paths and cycles. The method we used can also be applied to find a family of counter-examples to a conjecture posed by P. Keevash and B. Sudakov [J. Comb. Theory, Ser. B 90, No. 1, 41–53 (2004; Zbl 1033.05042)] concerning the maximum number of edges not contained in any monochromatic copy of \(H\) in a 2-edge-coloring of \(K_n\).

MSC:

05C35 Extremal problems in graph theory
05C30 Enumeration in graph theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abbott, H. L.; Hanson, D.; Sauer, H., Intersection theorems for systems of sets, J. Comb. Theory, Ser. A, 12, 381-389 (1972) · Zbl 0247.05004
[2] Balachandran, N.; Khare, N., Graphs with restricted valency and matching number, Discrete Math., 309, 4176-4180 (2009) · Zbl 1218.05120
[3] C. Chen, J. Ma, Y. Qiu, L. Yuan, Edges not in monochromatic copies of a non-bipartite graph, manuscript.
[4] Chen, G.; Gould, R. J.; Pfender, F.; Wei, B., Extremal graphs for intersecting cliques, J. Comb. Theory, Ser. B, 89, 159-171 (2003) · Zbl 1031.05069
[5] Chvátal, V.; Hanson, D., Degrees and matchings, J. Comb. Theory, Ser. B, 20, 128-138 (1976) · Zbl 0324.05119
[6] Erdős, P.; Stone, A. H., On the structure of linear graphs, Bull. Am. Math. Soc., 52, 1089-1091 (1946) · Zbl 0063.01277
[7] Erdős, P.; Gallai, T., On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hung., 10, 337-356 (1959) · Zbl 0090.39401
[8] Erdős, P., Über ein Extremalproblem in der Graphentheorie, Arch. Math. (Basel), 13, 122-127 (1962), (German)
[9] Erdős, P.; Simonovits, M., A limit theorem in graph theory, Studia Sci. Math. Hung., 1, 51-57 (1966) · Zbl 0178.27301
[10] Erdős, P.; Füredi, Z.; Gould, R. J.; Gunderson, D. S., Extremal graphs for intersecting triangles, J. Comb. Theory, Ser. B, 63, 89-100 (1995) · Zbl 0822.05036
[11] Füredi, Z.; Simonovits, M., The history of degenerate (bipartite) extremal graph problems, (Erdős centennial. Erdős centennial, Bolyai Soc. Math. Stud., vol. 25 (2013), János Bolyai Math. Soc.: János Bolyai Math. Soc. Budapest), 169-264 · Zbl 1296.05098
[12] Gallai, T., Neuer Beweis eines Tutte’schen Satzes, Magy. Tud. Akad. Mat. Kut. Intéz. Közl., 8, 135-139 (1963) · Zbl 0129.39802
[13] Glebov, R., Extremal graphs for clique-paths
[14] Hou, X.; Qiu, Y.; Liu, B., Extremal graph for intersecting odd cycles, Electron. J. Comb., 23, Article 2.29 pp. (2016) · Zbl 1337.05062
[15] Keevash, P.; Sudakov, B., On the number of edges not covered by monochromatic copies of a fixed graphs, J. Comb. Theory, Ser. B, 108, 41-53 (2004) · Zbl 1033.05042
[16] Liu, H., Extremal graphs for blow-ups of cycles and trees, Electron. J. Comb., 20, 1, Article 65 pp. (2013) · Zbl 1266.05074
[17] Liu, H.; Pikhurko, O.; Sharifzadeh, M., Edges not in any monochromatic copy of a fixed graph, J. Comb. Theory, Ser. B, 135, 16-43 (2019) · Zbl 1404.05056
[18] Ma, J., On edges not in monochromatic copies of a fixed bipartite graph, J. Comb. Theory, Ser. B, 132, 240-248 (2017) · Zbl 1367.05077
[19] Moon, J. W., On independent complete subgraphs in a graph, Can. J. Math., 20, 95-102 (1968) · Zbl 0153.54201
[20] Ni, Z.; Kang, L.; Shan, E.; Zhu, H., Extremal graphs for blow-ups of keyrings, Graphs Comb., 36, 1827-1853 (2020) · Zbl 1472.05080
[21] Simonovits, M., A method for solving extremal problems in graph theory, stability problems, (Theory of Graphs. Theory of Graphs, Proc. Colloq., Tihany, 1966 (1968), Academic Press: Academic Press New York), 279-319 · Zbl 0164.24604
[22] Simonovits, M., Extremal graph problems with symmetrical extremal graphs. Additional chromatic conditions, Discrete Math., 7, 349-376 (1974) · Zbl 0274.05113
[23] Simonovits, M., The extremal graph problem of the icosahedron, J. Comb. Theory, Ser. B, 17, 69-79 (1974) · Zbl 0279.05124
[24] Turán, P., On an extremal problem in graph theory, Mat. Fiz. Lapok, 48, 436-452 (1941), (in Hungarian) · Zbl 0026.26903
[25] Wang, A.; Hou, X.; Liu, B.; Ma, Y., The Turán number for the edge blow-up of trees, Discrete Math., 344, Article 112627 pp. (2021) · Zbl 1473.05137
[26] Yuan, L., Extremal graphs for odd wheels, J. Graph Theory, 98, 691-707 (2021) · Zbl 1522.05233
[27] Yuan, L., Extremal graphs for the k-flower, J. Graph Theory, 89, 26-39 (2018) · Zbl 1432.05057
[28] Zhu, H.; Kang, L.; Shan, E., Extremal graphs for odd-ballooning of paths and cycles, Graphs Comb., 36, 755-766 (2020) · Zbl 1442.05109
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.