Ordinary and Spectral Extremal Problems on Vertex Disjoint Copies of Even Fans

Abstract

Let ex(n, F) and spex(n, F) be the maximum size and spectral radius among all F-free graphs with fixed order n, respectively. A fan is a graph P₁ ∨ P_s (join of a vertex and a path of order s) for s ≥ 3, and it is called an even fan if s is even. In this paper, we study ex(n, t(P₁ ∨ P_2k)), spex(n, t(P₁ ∨ P_2k)) with t ≥ 1 and k ≥ 3 and characterize the corresponding extremal graphs for sufficiently large n.

Keywords

Graph size / spectral radius / extremal graphs / 05C35 / 05C50

References

[1] Brouwer AE, Haemers WH. Spectra of Graphs, 2012, New York, Springer

[2] Chen M, Liu A, Zhang X. Spectral extremal results with forbidding linear forests. Graphs Combin., 2019, 35(1): 335-351

[3] Chen M., Liu A., Zhang X., On the spectral radius of graphs without a star forest. Discrete Math., 2021, 344 (4): Paper No. 112269, 12 pp.

[4] Chvátal V, Hanson D. Degrees and matching. J. Combinatorial Theory Ser. B, 1976, 20(2): 128-138

[5] Cioabă S., Desai D.N., Tait M., The spectral radius of graphs with no odd wheels. European J. Combin., 2022, 99: Paper No. 103420, 19 pp.

[6] Cioabă S., Feng L., Tait M., Zhang X., The maximum spectral radius of graphs without friendship subgraphs. Electron. J. Combin., 2020, 27 (4): Paper No. 4.22, 19 pp.

[7] Desai DN, Kang L, Li Y, Ni Z, Tait M, Wang J. Spectral extremal graphs for intersecting cliques. Linear Algebra Appl., 2022, 644: 234-258

[8] Fang L., Zhai M., Lin H., Spectral extremal problem on t copies of ℓ-cycles. Electron. J. Combin., 2024, 31 (4): Paper No. 4.17, 30 pp.

[9] Feng L, Yu G, Zhang X. Spectral radius of graphs with given matching number. Linear Algebra Appl., 2007, 422(1): 133-138

[10] Füredi Z. Turán type problems. Surveys in Combinatorics, 1991 (Guildford, 1991), 1991, 166: 253-300

[11] Kövari T, Sós VT, Turán P. On a problem of K. Zarankiewicz. Colloq. Math., 1954, 3: 50-57

[12] Luo Y, Ni Z, Dong Y. Spectral extremal graphs for disjoint odd wheels. Linear Algebra Appl., 2025, 710: 243-266

[13] Minc H. Nonnegative Matrices, 1988, New York, John Wiley & Sons, Inc.

[14] Moon J. On independent complete subgraphs in a graph. Canadian J. Math., 1968, 20: 95-102

[15] Ni Z., Wang J., Kang L., Spectral extremal graphs for disjoint cliques. Electron. J. Combin., 2023, 30 (1): Paper No. 1.20, 16 pp.

[16] Nikiforov V. Stability for large forbidden subgraphs. J. Graph Theory, 2009, 62(4): 362-368

[17] Nikiforov V. The spectral radius of graphs without paths and cycles of specified length. Linear Algebra Appl., 2010, 432(9): 2243-2256

[18] Pikhurko O. A note on the Turán function of even cycles. Proc. Amer. Math. Soc., 2012, 140(11): 3687-3692

[19] Simonovits M. A method for solving extremal problems in graph theory, stability problems. Theory of Graphs (Proc. Colloq., Tihany, 1966), 1968, New York, Academic Press279319

[20] Simonovits M. Extremal graph problems with symmetrical extremal graphs. Additional chromatic conditions. Discrete Math., 1974, 7: 349-376

[21] Xiao C., Zamora O., A note on the Turán number of disjoint union of wheels. Discrete Math., 2021, 344 (11): Paper No. 112570, 7 pp.

[22] Yuan L. Extremal graphs for odd wheels. J. Graph Theory, 2021, 98(4): 691-707

[23] Yuan Q., Liu R., Yuan J., The spectral radius of H_2k-free graphs. Appl. Math. Comput., 2024, 469: Paper No. 128560, 14 pp.

RIGHTS & PERMISSIONS

Peking University