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)\leq \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}_{ \geq 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\geq k\geq 5$ and let $t=\left\lfloor\frac{ k-1}{ 2}\right\rfloor$. Let $G$ be a $2$-connected $n$-vertex $\mathcal{ C}_{ \geq k}$-free graph with the maximum $\mathcal{ P}(G)$ where $\mathcal{ P}(G)$ is feasible. Then, $G\in \mathcal{ G}^1_{ n,k}=\{ W_{ n,k,s}=K_{ s}\vee ((n-k+s)K_1\cup K_{ k-2s}): 2\leq s\leq t\}$. (ii) Let $n\geq k\geq 4$ and let $t=\left\lfloor\frac{ k}{ 2}\right\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}^2_{ n,k}=\{ W_{ n,k-1,s}=K_{ s}\vee ((n-k+s+1)K_1\cup K_{ k-2s-1}): 1\leq s\leq 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}^3_{ n,k}=\{ K_s\vee ((n-2k+s-1)K_1\cup K_{ 2k-2s+1}):1\leq s\leq k\}$ when $n\geq 2k+2$. Directly derived from these three main results, we obtain a series of applications in Tur\'an-type problems, generalized Tur\'an-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.
Categories: math.CO