2023/12/13 by Jiangdong Ai, Ai, Jiangdong, Hui Lei +5 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2312.08226
openalex publication_date 2023/12/13 · openalex created_date 2023/12/15 · openalex updated_date 2026/07/28
Let G be a connected graph and P(G) a graph parameter. We say that P(G) is feasible if P(G) satisfies the following properties: (I) P(G)≤ P(Guv), if Guv=G[u→ v] for any u,v, where Guv is the graph obtained by applying Kelmans operation from u to v; (II) P(G) <P(G+e) for any edge e∉ E(G). Let Pk be a path of order k, C≥ k the set of all cycles of length at least k and Mk+1 a matching containing k+1 independent edges. In this paper, we mainly prove the following three results: (i) Let n≥ k≥ 5 and let t=\lfloor(k-1)/(2)\rfloor. Let G be a 2-connected n-vertex C≥ k-free graph with the maximum P(G) where P(G) is feasible. Then, G∈ G1n,k=\Wn,k,s=Ks\vee ((n-k+s)K1∪ Kk-2s): 2≤ s≤ t\. (ii) Let n≥ k≥ 4 and let t=\lfloor(k)/(2)\rfloor-1. Let G be a connected n-vertex Pk-free graph with the maximum P(G) where P(G) is feasible. Then, G∈ G2n,k=\Wn,k-1,s=Ks\vee ((n-k+s+1)K1∪ Kk-2s-1): 1≤ s≤ t\. (iii) Let G be a connected n-vertex Mk+1-free graph with the maximum P(G) where P(G) is feasible. Then, G≅ Kn when n=2k+1 and G∈ G3n,k=\Ks\vee ((n-2k+s-1)K1∪ K2k-2s+1):1≤ s≤ k\ when n≥ 2k+2. Directly derived from these three main results, we obtain a series of applications in Turán-type problems, generalized Turán-type problems, powers of graph degrees in extremal graph theory, and problems related to spectral radius, and signless Laplacian spectral radius in spectral graph theory.