Graph operations and a unified method for kinds of Turán-type problems on paths, cycles and matchings

Abstract

Let $G$ be a connected graph and $\mathcal{P}(G)$ a graph parameter. We say that $\mathcal{P}(G)$ is feasible if $\mathcal{P}(G)$ satisfies the following properties: (I) $\mathcal{P}(G)\le \mathcal{P}(G_{uv})$, if $G_{uv}=G[u\to v]$ for any $u,v$, where $G_{uv}$ is the graph obtained by applying Kelmans operation from $u$ to $v$; (II) $\mathcal{P}(G)<\mathcal{P}(G+e)$ for any edge $e\notin E(G)$. Let $P_k$ be a path of order $k$, ${\mathcal{C}}_{\ge k}$ the set of all cycles of length at least $k$ and $M_{k+1}$ a matching containing $k+1$ independent edges. In this paper, we mainly prove the following three results: (i) Let $n\ge k\ge 5$ and let $t=\lfloor \frac{k-1}{2}\rfloor$. Let $G$ be a $2$-connected $n$-vertex ${\mathcal{C}}_{\ge k}$-free graph with the maximum $\mathcal{P}(G)$ where $\mathcal{P}(G)$ is feasible. Then, $G\in {\mathcal{G}}_{n,k}^1=\{W_{n,k,s}=K_s\vee ((n-k+s)K_1\cup K_{k-2s}):2\le s\le t\}$. (ii) Let $n\ge k\ge 4$ and let $t=\lfloor \frac{k}{2}\rfloor -1$. Let $G$ be a connected $n$-vertex $P_k$-free graph with the maximum $\mathcal{P}(G)$ where $\mathcal{P}(G)$ is feasible. Then, $G\in {\mathcal{G}}_{n,k}^2=\{W_{n,k-1,s}=K_s\vee ((n-k+s+1)K_1\cup K_{k-2s-1}):1\le s\le t\}.$ (iii) Let $G$ be a connected $n$-vertex $M_{k+1}$-free graph with the maximum $\mathcal{P}(G)$ where $\mathcal{P}(G)$ is feasible. Then, $G\cong K_n$ when $n=2k+1$ and $G\in {\mathcal{G}}_{n,k}^3=\{K_s\vee ((n-2k+s-1)K_1\cup K_{2k-2s+1}):1\le s\le k\}$ when $n\ge 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.

V2