1 Introduction
The main goal of this article is to develop a method that provides a unified approach for solving some Turán-type and generalized Turán-type problems, degree power problems, and extremal spectra problems (mainly under spectral radius conditions and signless Laplacian spectral radius conditions) on paths, cycles, and matchings. Before our work, all topics mentioned here have almost exclusively been studied independently and through distinct approaches. Now, we will give some basic definitions here, and more notation will be given in Section 1.4.
A graph
$G=G(V,E)$
is connected if, for every partition of its vertex set into two nonempty sets X and Y, there is an edge with one end in X and one end in Y. If there is a vertex v such that
$G\backslash \{v\}$
is not connected, then we say that such a vertex v is a cut-vertex of G. If there is no cut-vertex in G, we say that G is
$2$
-connected. Let
$G_1$
and
$G_2$
be two graphs. We use
$G_1\cup G_2$
to denote the disjoint union of
$G_1$
and
$G_2$
, and
$G_1\vee G_2$
to denote the join of
$G_1$
and
$G_2$
, i.e., in addition to the edges in
$G_1\cup G_2$
, it contains all possible edges from
$G_1$
to
$G_2$
.
In the following, we will briefly review each of these topics. It is a bit long, so for those already familiar with these subjects, we encourage you to proceed to the subsequent sections (Sections 2 and 4).
1.1 Turán-type and generalized Turán-type theorems on paths, cycles, and matchings
A fundamental result in graph theory asserts that any graph with n vertices and
$m\geq n$
edges has a cycle. Strengthening this fact, a cornerstone result attributed to Erdős and Gallai [Reference Erdős and Gallai7] says that if an n-vertex graph has at least
$m\geq n$
edges, then there is a cycle of length at least
$\frac {2m}{n-1}$
. Given a family of graphs
$\mathcal {H}$
, we denote the Turán number of
$\mathcal {H}$
by
$ex(n,\mathcal {H})$
, that is, the maximum number of edges in an n-vertex graph which contains no H as a subgraph for each
$H\in \mathcal {H}$
. When
$\mathcal {H}=\{H\}$
, we use
$ex(n,H)$
instead of
$ex(n,\mathcal {H})$
. In this language, the Erdős–Gallai Theorem is equivalent to
$ex(n,{\mathcal {C}}_{\geq k})=\frac {(k-1)(n-1)}{2}$
, where
$\mathcal {C}_{\geq k}$
is the set of all cycles of lengths at least k,
$3\leq k\leq n$
. A graph consisting of
$\frac {n-1}{k-2}$
cliques of size
$k-1$
such that if we regard each clique as a vertex, then the resulting graph is a tree, where
$n-1$
is divisible by
$k-2$
, is the extremal graph.
Since the extremal graph contains a cut-vertex, the classical Erdős–Gallai Theorem can be improved if we assume that G is
$2$
-connected. In this setting, among the improvements due to Woodall [Reference Woodall27], Lewin [Reference Lewin14], Faudree and Schelp [Reference Faudree and Schelp8], and Kopylov [Reference Kopylov13], the following theorem on cycles due to Kopylov is the strongest in some sense.
Define
$W_{n,k,s}$
to be a graph on n vertices in which its vertex set can be partitioned into three subsets
$X,Y,Z$
, in which
$|X|=s$
,
$|Y|=k-2s$
, and
$|Z|=n-(k-s)$
, and the edge set consists of all possible edges between X and Z and all edges in
$X\cup Y$
. The graphs
$W_{n,k,2}$
and
$W_{n,k,t}$
show that Kopylov’s theorem is sharp (see Figure 1).
$W_{14,11,3}$
.
Theorem 1.1 (Kopylov [Reference Kopylov13])
Let
$n\geq k\geq 5$
and let
$t=\left \lfloor \frac {k-1}{2}\right \rfloor $
. If G is a 2-connected n-vertex graph with
$e(G)>\max \{e(W_{n,k,2}),e(W_{n,k,t})\}$
, then G has a cycle of length at least k.
The path version theorem is similar to Theorem 1.1, where equality case was determined by Balister, Győri, Lehel, and Schelp in [Reference Balister, Győri, Lehel and Schelp3].
Theorem 1.2 (Kopylov [Reference Kopylov13] and Balister, Győri, Lehel, and Schelp [Reference Balister, Győri, Lehel and Schelp3])
Let
$n\geq k\geq 4$
and
$t=\left \lfloor \frac {k}{2}\right \rfloor -1$
. If G is a connected graph on n vertices with
$$ \begin{align*}e(G)\geq \max\left\{\binom{k-2}{2}+n-k+2,\binom{\lceil\frac{k}{2}\rceil}{2}+(\left\lfloor\frac{k}{2}\right\rfloor-1)\left(n-\left\lceil\frac{k}{2}\right\rceil\right)\right\}, \end{align*} $$
then G contains a path of order k, unless G is either
$W_{n,k-1,1}$
or
$W_{n,k-1,t}$
.
Another important theorem in extremal graph theory is Erdős–Gallai’s matching theorem. Akiyama and Frankl [Reference Akiyama and Frankl1] gave a short proof of the Erdős–Gallai Theorem by the shifting method.
Theorem 1.3 (Erdős–Gallai [Reference Erdős and Gallai7])
If G is an n-vertex graph with
$$ \begin{align*}e(G)\geq \max \left\{\binom{2k+1}{2}, \binom{k}{2}+k(n-k)\right\}, \end{align*} $$
then G contains an
$M_{k+1}$
, unless
$G=K_{2k+1}$
or
$G=K_k\vee ((n-k)K_1)$
.
Rather than determining the maximum number of edges, Alon and Shikhelman [Reference Alon and Shikhelman2] studied the function
$ex(n,F,H),$
which is defined as the maximum number of copies of F in an H-free n-vertex graph. This type of problem is called the Generalized Turán Problem. Note that when
$F=K_2$
, we are back to the classic Turán Problem. Let
$N_s(G)$
denote the maximum number of unlabeled copies of
$K_s$
in G. By using Kopylov’s technique, Luo [Reference Luo20] extended Kopylov’s theorem on cycles and paths to its clique versions. Győri, Salia, Tompkins, and Zamora [Reference Győri, Salia, Tompkins and Zamora11] obtained some extensions by counting stars. As we see later, the numbers of such certain subgraphs are defined as weakly-feasible parameters by us in this article, and we can give a unified method to deal with them.
Very recently, Theorem 1.1 has received much attention (see [Reference Lu, Yuan and Zhang19–Reference Ma and Ning21]). The stability form of Kopylov’s theorem seems to play an important role in solving numerous conjectures and problems from different aspects of graph theory, for example, the classical Anti-Ramsey conjecture and problems in spectral graph theory (see [Reference Li and Ning17, Reference Li, Liu and Feng18, Reference Yuan28]).
1.2 Degree power problems on paths and cycles
Given a graph G of order n with degree sequence
$d_1,d_2,\dots , d_n$
, we use
$\sum _{i=1}^{n}d_i^p$
, where
$p\geq 1$
to denote the degree power of G. Note that when
$p=1$
,
$\sum _{i=1}^{n}d_i=2e(G)$
. This parameter, which is also known as the general zeroth-order Randić index, is well-studied in chemical graph theory. There is much interest in the study of the maximum degree power sums of graphs that do not have certain subgraphs. Our work mainly focuses on forbidding long paths and cycles in graphs.
Caro and Yuster [Reference Caro and Yuster5] determined the maximum degree power in graphs that are
$P_k$
-free, assuming that n is considerably larger than k, where
$P_k$
denotes the path of order k. They also provided a characterization of the extremal graphs.
Theorem 1.4 (Caro and Yuster)
Let
$k\geq 4$
,
$t=\lfloor \frac {k}{2}\rfloor -1,$
and
$p\geq 2$
. There exists
$n_0(k)$
such that for any integer
$n>n_0(k)$
, if G is an n-vertex
$P_{k}$
-free graph with the maximum degree power
$\sum _{v\in V(G)}d^p(v)$
, then G is
$W_{n,k-1,t}$
. Furthermore,
$W_{n,k-1,t}$
is the unique extremal graph.
To obtain the concrete magnitude relationship between n and k seems to be difficult. They guessed the same conclusion still holds under the weaker condition, i.e.,
$n=\Omega (k^2)$
. Confirming a conjecture by Caro and Yuster, in this article, we give a solution to the connected version of Caro–Yuster’s problem. The main result is as follows.
Theorem 1.5 Let
$k\geq 4$
and
$n\geq 2k$
. Let G be a connected n-vertex
$P_{k}$
-free graph with the maximum degree power
$\sum _{v\in V(G)}d^p(v),$
where
$p\geq 2$
. Then, G is
$W_{n,k-1,t}$
, where
$t=\lfloor \frac {k}{2}\rfloor -1$
.
Nikiforov [Reference Nikiforov22] determined the maximum value of degree powers in graphs that forbid even cycles of a fixed size. In this article, we give the following result.
Theorem 1.6 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 degree power
$\sum _{v\in V(G)}d^p(v),$
where
$p\geq 2$
, Then, G is
$W_{n,k,1}$
or
$W_{n,k,t}$
.
1.3 Spectral extrema on paths and cycles
Let G be a graph and
$A:=A(G)$
be its adjacency matrix. Let
$\lambda _1\geq \lambda _2\geq \cdots \geq \lambda _n$
be all eigenvalues of A. The spectral radius of G, denoted by
$\lambda (G)$
, is defined to be
$\max \{|\lambda _i|:1\leq i\leq n\}$
. The signless Laplacian spectral radius of G, denoted by
$q(G)$
, is the largest eigenvalue of
$A(G)+D(G)$
, where
$D(G)$
is the degree matrix of G. For a given graph H, we denote by
$\mathrm{spex}(n,H)$
(
$\mathrm{spex}_{con}(n,H)$
,
$\mathrm{spex}_{2-con}(n,H)$
) the maximum spectral radius of a (connected, 2-connected) graph on n vertices which contains no H as a subgraph. We use
$\mathrm{sspex}(n,H)$
(
$\mathrm{sspex}_{con}(n,H)$
) to denote the maximum signless spectral radius of a (connected) graph on n vertices which contains no H as a subgraph.
In contrast to classical extremal graph theory, spectral extremal graph theory is a relatively young and active branch. For a survey on its developments and open problems, we refer to [Reference Nikiforov24]. Until now, very little was known about complete pictures of certain classes of graphs.
In this article, we focus on the spectra extrema of graphs without long paths or long cycles. We denote
$K_k\vee (n-k)K_1$
by
$S_{n,k}$
, and
$K_k\vee ((n-k-2)K_1\cup K_2)$
by
$S^+_{n,k}$
for simplicity. This problem can be dated back at least to [Reference Nikiforov23]. Nikiforov [Reference Nikiforov23] proved that
$\mathrm{spex}(n, P_{2k+2})=\lambda (S_{n,k})$
and
$\mathrm{spex}(n, P_{2k+3})=\lambda (S^+_{n,k})$
for
$n\geq 2^{4k}$
and
$k\geq 1$
. Gao and Hou [Reference Gao and Hou10] proved that
$\mathrm{spex}(n,\mathcal {C}_{\geq 2k+1})=\lambda (S_{n,k})$
and
$\mathrm{spex}(n,\mathcal {C}_{\geq 2k+2})=\lambda (S^+_{n,k})$
for
$k\geq 2$
and
$n\geq 13k^2$
. We will consider what happens when
$k=\Theta (n)$
, in particular, when the forbidden path or cycle is spanning or nearly spanning. For this case, Fiedler and Nikiforov [Reference Fiedler and Nikiforov9] proved
$\mathrm{spex}(n,P_{n})=\lambda (K_{n-1}\cup K_1)$
. A natural problem is to determine all the values of
$\mathrm{spex}(n, P_k)$
for any
$4\leq k< n$
. This question was originally asked by Nikiforov [Reference Nikiforov23].Footnote
1
As far as we know, this difficult problem is still wide open.
In this article, we study the following two problems. The first one includes the problem just mentioned.
Problem 1 Let
$k\geq 4$
and
$n\geq k$
be two integers. Determine the function
$\mathrm{spex}_{con}(n,P_{k})$
and
$\mathrm{spex}(n,P_k)$
.
Problem 2 Let
$k\geq 5$
and
$n\geq k$
be two integers. Determine the function
$\mathrm{spex}_{2-con}(n,\mathcal {C}_{\geq k})$
.
In this article, we solve these two problems above completely. Our results cover all possible values of n and k.
Theorem 1.7 Let
$n\geq k\geq 4$
and
$t=\left \lfloor \frac {k}{2}\right \rfloor -1$
. Let G be an n-vertex
$P_{k}$
-free graph with the maximum spectral radius. Then,
$\lambda (G)=\max \{\lambda (W_{n,k-1,s}),\lambda (K_{k-1}):1\leq s\leq t\}$
.
We would like to point out that this is the first time introducing the Kopylov-style technique to spectral graph theory. In addition, we also prove an analog for graphs with a given matching number.
For the signless Laplacian spectral version of problems on paths, Nikiforov and Yuan [Reference Nikiforov and Yuan25] proved that for
$k\geq 1$
,
$n\geq 7k^2$
, and an n-vertex graph G, if
$q(G)>q(S_{n,k}),$
then G contains a
$P_{2k+2}$
; if
$q(G)>q(S^+_{n,k}),$
then G contains a
$P_{2k+3}$
. In this article, we also give solutions to the signless Laplacian spectral radius versions of Problems 1 and 2.
1.4 Terminology and notation
Let
$G=G(V,E)$
be a graph and let
$X\subseteq V$
. The subgraph of G induced by X is denoted by
$G[X]$
. The vertices in
$N_G(v)$
are neighbors of v. The degree of v in G, denoted by
$d_G(v)$
, equals to
$|N_G(v)|$
. Denote
$N_G(v)\cup \{v\}$
by
$N_G[v]$
. We may omit the subscripts sometimes when it is clear from the context. We use
$K_1$
to denote an isolated vertex, and
$kK_1$
to denote an isolated set of k vertices. For a subset
$S\subseteq V(G)$
(we may also use S to denote the graph induced by S sometimes), we denote by
$G-S$
the subgraph of G induced by
$V(G)\backslash V(S)$
.
A matching in a graph is a set of pairwise nonadjacent edges. We use
$M_k$
to denote a matching of size k. A maximum matching is one which covers as many vertices as possible. We use
$c(G)$
and
$\nu (G)$
to denote the length of a longest cycle and the size of a maximum matching in G, respectively. Given two sequences
$d=(d_1,d_2,\dots ,d_n)$
and
$c=(c_1,c_2,\dots ,c_n)$
in decreasing order, we say
$d>c$
if there exists a
$k\in [n]=\{1,2,\dots ,n\}$
such that
$d_k> c_k$
and
$d_i=c_i$
for all
$1\leq i<k$
. Note that this is lexicographical ordering.
1.5 Outline
This article is organized as follows. In the first section, we provide an overview of the background of the relevant topics. Subsequently, in Section 2, we will briefly outline the contributions made by our research. In Sections 3 and 4, we will explain how our research findings can be used in different problems. Specifically, we explain how different graph parameters can be shown in a unified way when we do not allow long cycles or long paths. In Section 5, we present the proofs of the main theorems along with necessary lemmas and tools. In the final section, we provide some comments.
2 Our contributions
We observe that many of the graph parameters mentioned in Section 1 behave similarly. We aim to generalize such parameters and analyze them systematically. The members in this type of graph parameters, called feasible (weakly) graph parameters, include the number of edges, spectral radius, signless Laplacian spectral radius, degree power, the number of s-cliques or
$K_{1,r}$
, etc.
Our new concept is based on Kelmans Operation, which was introduced by Kelmans in [Reference Kelmans12]. (The original form of Kelmans Operation does not care about the adjacency of two given vertices. However, we also divide it into two types of operations according to the adjacency for the sake of use later.)
Definition 1
-
(i) Let G be a graph and
$xy\in E(G)$
. The graph after a Kelmans Operation (KO in short) of G from x to y, is denoted by
$G'=G[x\rightarrow y]$
, if
$G'$
satisfies
$V(G')=V(G)$
and
$E(G')=(E(G)\backslash \{wx:w\in N_G(x)\backslash N_G[y]\})\cup \{wy:w\in N_G(x)\backslash N_G[y]\}$
. -
(ii) Let G be a graph and
$xy\notin E(G)$
. The graph after an extended Kelmans Operation (EKO in short) of G from x to y, is denoted by
$G'=G[x\rightarrow y]$
, if
$G'$
satisfies
$V(G')=V(G)$
and
$E(G')=(E(G)\backslash \{wx:w\in N_G(x)\backslash N_G[y]\})\cup \{wy:w\in N_G(x)\backslash N_G[y]\}$
.
Observe that
$G[x\rightarrow y]$
is isomorphic to
$G[y\rightarrow x]$
. Figure 2 is an example of KO.
$G[y\rightarrow x]$
.
A graph parameter is a function
$\mathcal {P}:\mathbb {G}\to \mathbb {R,}$
where
$\mathbb {G}$
is the set of finite graphs and
$\mathbb {R}$
is the set of real numbers.
Definition 2 Let G be a connected graph and
$\mathcal {P}(G)$
be 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 vertices
$u,v$
; -
(II)
$\mathcal {P}(G) <\mathcal {P}(G+e)$
for any new edge
$e\notin E(G)$
with
$V(e)\cap V(G)\neq \emptyset $
. Here, the edge e may contain a new vertex outside
$V(G)$
.
If H is a connected proper subgraph of a connected graph G, then
$\mathcal {P}(H)<\mathcal {P}(G)$
as we can apply (II) of Definition 2 repeatedly.
By combining the Kopylov-type technique with Kelmans Operation (together with some structural analysis), we prove the following three main results. The proofs are postponed to Section 5.
Theorem 2.1 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,
$$ \begin{align*}G\in \mathcal{G}^1_{n,k}=\{K_{s}\vee ((n-k+s)K_1\cup K_{k-2s}): 2\leq s\leq t\}.\end{align*} $$
Theorem 2.2 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,
$$ \begin{align*}G\in \mathcal{G}^2_{n,k}=\{K_{s}\vee ((n-k+s+1)K_1\cup K_{k-2s-1}): 1\leq s\leq t\}.\end{align*} $$
Theorem 2.3 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
$$ \begin{align*}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\}\end{align*} $$
when
$n\geq 2k+2$
.
Based on these theorems, we can easily give alternative proofs of some known results mentioned in Section 1. In addition, we fully or partially solve some open problems.
3 On feasible parameters of graphs
In this section, we show that several classical graph parameters of a connected graph, including the number of edges, degree power, spectral radius, and signless Laplacian spectral radius, are feasible.
Theorem 3.1 Let G be a connected graph and let
$p\geq 2$
be a real. The degree power
$\sum _{v\in V(G)}d^p(v)$
of G is feasible.
Proof Denote
$\sum _{v\in V(G)}d^p(v)$
of G by
$D(G)$
. Given two vertices u and v, let
$x=|N(u)\backslash N[v]|$
,
$y=|N(v)\backslash N[u]|$
and
$z=|N(u)\cap N(v)|$
if
$uv\notin E(G)$
, and
$z=|N(u)\cap N(v)|+1$
if
$uv\in E(G)$
. Without loss of generality, we assume
$uv\notin E(G)$
. Let
$G_{uv}:=G[u\rightarrow v]$
. We have that
$$ \begin{align*}D(G_{uv})=D(G)-((x+z)^p+(y+z)^p)+((x+y+z)^p+z^p).\end{align*} $$
Here, we assume
$x+y>0$
. Otherwise, we can easily get
$D(G_{uv})=D(G)$
. Let
$f(x)=x^p$
. Then,
$f(x)$
is a strictly convex function. By Jensen’s Inequality, we have that
$$ \begin{align} \frac{x}{x+y}f(z)+\frac{y}{x+y}f(x+y+z)\geq&f(y+z). \end{align} $$
$$ \begin{align} \frac{y}{x+y}f(z)+\frac{x}{x+y}f(x+y+z)\geq&f(x+z). \end{align} $$
$$ \begin{align*}f(z)+f(x+y+z)\geq f(x+z)+f(y+z).\end{align*} $$
Thus,
$D(G_{uv})\geq D(G)$
. Obviously,
$D(G+e)>D(G)$
for any
$e\notin E(G)$
. So,
$\sum _{v\in V(G)}d^p(v)$
is feasible.
Theorem 3.2 The number of edges of a connected graph is feasible.
Proof It is easy to check that Kelmans operation preserves the number of edges in G, and
$e(G+uv)>e(G)$
for any new edge
$uv$
. This proves the theorem.
A matrix
$A\in R^{n\times n}$
is said to be irreducible if it cannot be transformed into a block upper triangular form by rearranging its rows and columns. Let A and B be two matrices. We say
$A\leq B$
if
$a_{i,j}\leq b_{i,j}$
for all
$i,j$
, where
$a_{i,j}$
and
$b_{i,j}$
are the elements in the i-th row and j-th column of matrices A and B, respectively. The following two lemmas are from Zhan [Reference Zhan29].
Lemma 1 (Zhan [Reference Zhan29])
Let A and B be two nonnegative square matrices of order n. If
$B\leq A$
,
$B\ne A$
, and A is irreducible, then
$\lambda (B) <\lambda (A)$
.
Lemma 2 (Zhan [Reference Zhan29])
Let A be a nonnegative square matrix. If B is a principal submatrix of
$A,$
then
$\lambda (B)\leq \lambda (A)$
. If A is irreducible and B is a proper principal submatrix of A, then
$\lambda (B)<\lambda (A)$
.
Let G be a graph on n vertices, and let
$A(G)$
be the adjacency matrix of G. Note that G is connected if and only if
$A(G)$
is irreducible.
The following are basic facts which can be deduced from above.
Lemma 3 Let G be a connected graph and
$xy\notin E(G)$
. Suppose
$G+xy$
is connected. Then, (i)
$\lambda (G+xy)>\lambda (G)$
and (ii)
$q(G+xy)>q(G)$
.
Lemma 4 Let G be a connected graph and let H be a proper subgraph of G. Then, (i)
$\lambda (G)>\lambda (H)$
and (ii)
$q(G)>q(H)$
.
Lemma 5 [Reference Csikvári6]
Let G be a connected graph and
$u,v\in V(G)$
(maybe
$uv\notin E(G)$
). Let
$G_{uv}:=G[u\rightarrow v]$
. Then,
$\lambda (G_{uv})\geq \lambda (G)$
.
Lemma 6 [Reference Li and Ning15]
Let G be a connected graph and
$u,v\in V(G)$
(maybe
$uv\notin E(G)$
). Let
$G_{uv}:=G[u\rightarrow v]$
. Then,
$q(G_{uv})\geq q(G)$
.
Thus, by the above lemmas, we have the following.
Theorem 3.3 The spectral radius of a connected graph is feasible.
Theorem 3.4 The signless Laplacian spectral radius of a connected graph is feasible.
Definition 3 Let G be a connected graph and
$\mathcal {P}(G)$
be a graph parameter. We say that
$\mathcal {P}(G)$
is weakly-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 vertices
$u,v\in V(G)$
; -
(II)
$\mathcal {P}(G) \leq \mathcal {P}(G+e)$
for every new edge
$e\notin E(G)$
with
$V(e)\cap V(G)\neq \emptyset $
.
Theorem 3.5 The number of s-cliques in a connected graph is weakly-feasible.
Proof Let G be a connected graph and
$n_s(G)$
denote the number of s-cliques. For any two vertices
$u,v\in V(G)$
, let
$G_{uv}:=G[u\to v]$
. Suppose K is an s-clique K. If
$|K\cap \{u,v\}|\in \{0,2\}$
, set
$K_{uv}=K$
. If K contains u but not v, set
$K_{uv}=G_{uv}[(K\setminus \{u\})\cup \{v\}]$
, which is an s-clique in
$G_{uv}$
.
Observe that if K is an s-clique containing neither u nor v in G, then K is still an s-clique in
$G_{uv}$
; if K is an s-clique containing both u and v in G, then K is still an s-clique in
$G_{uv}$
; if K is an s-clique containing u but not v in G, then
$K_{uv}$
is an s-clique in
$G_{uv}$
. For any two distinct s-cliques
$K,K'\subseteq G$
containing u but not v, as
$K\neq K'$
,
$V(K)\neq V(K')$
. Then, we can see
$V(K_{uv})\neq V(K^{\prime }_{uv})$
. This means that
$K_{uv}\neq K^{\prime }_{uv}$
for this case. If K is an s-clique containing v but not u in G, then K is still an s-clique in
$G_{uv}$
. Thus, we find a bijection
$f: K\rightarrow K_{uv}$
, and so
$n_s(G)\leq n_s(G_{uv})$
.
Analogously, we can get the following result.
Theorem 3.6 The number of
$K_{1,r}$
in a connected graph is weakly-feasible.
4 Implications
All corollaries in this section assume Theorems 2.1–2.3, whose proofs are postponed to Section 5. From the proofs of our main theorems, it is not hard to check that if we replace “feasible” with “weakly-feasible,” then we could get the following results accordingly.
Theorem 4.1 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 weakly-feasible. Then,
$\mathcal {P}(G)\leq \max \{\mathcal {P}(K_{s}\vee ((n-k+s)K_1\cup K_{k-2s})): 2\leq s\leq t\}$
.
Theorem 4.2 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 weakly-feasible. Then,
$\mathcal {P}(G)\leq \max \{\mathcal {P}(K_{s}\vee ((n-k+s+1)K_1\cup K_{k-2s-1})): 1\leq s\leq t\}.$
Theorem 4.3 Let G be a connected n-vertex
$M_{k+1}$
-free graph with the maximum
$\mathcal {P}(G),$
where
$\mathcal {P}(G)$
is weakly-feasible. Then,
$\mathcal {P}(G)\leq \max \{\mathcal {P}(K_s\vee ((n-2k+s-1)K_1\cup K_{2k-2s+1})):1\leq s\leq k,\mathcal {P}(K_{2k+1})\}$
.
4.1 Turán-type results and generalized Turán-type results
Based on our main theorems, we can give an alternative proof for each of the following known results.
Theorem 4.4 (Erdős–Gallai [Reference Erdős and Gallai7] and Akiyama–Frankl [Reference Akiyama and Frankl1])
Let
$n\geq 2k+1$
. If G is a graph with maximum number of edges such that G is
$M_{k+1}$
-free, then
$G\cong K_{2k+1}\cup (n-2k-1)K_1$
or
$G\cong S_{n,k}$
.
Proof Suppose that G is connected. If
$n\geq 2k+2$
, then
$|E(G)|=\max \{(n-2k+s-1)s+\binom {2k-s+1}{2}: 1\leq s\leq k\}$
by Theorem 2.3. Let
$f(s)=(n-2k+s-1)s+\binom {2k-s+1}{2}$
. Observe that
$f(s)$
is a convex function of s in
$[1,k]$
, so
$G\cong S_{n,k}$
or
$G\cong K_1\vee ((n-2k)K_1\cup K_{2k-1})$
. Observe that if
$k=1,$
we have
$S_{n,k}\cong K_1\vee ((n-2k)K_1\cup K_{2k-1})$
. So, we may assume
$k\ne 1$
. Now, let
$f_1(n,t)=|E(S_{n,t})|=nt-\frac {t^2}{2}-\frac {t}{2}$
,
$f_2(n,t)=|E(K_1\vee ((n-2t)K_1\cup K_{2t-1}))|=n+2t^2-3t$
and
$f_3(2t+1,t)=|E(K_{2t+1})|=2t^2+t$
. By elementary calculus, we have when
$2k+1\leq n< 4k$
,
$f_2(n,k)<f_3(n,k)$
; when
$n>\frac {5k}{2}$
,
$f_2(n,k)<f_1(n,k)$
; and when
$n>\frac {5k}{2}+\frac {3}{2}$
,
$f_1(n,k)>f_3(n,k)$
, which means
$|E(K_1\vee ((n-2k)K_1\cup K_{2k-1}))|<\max \{|E(K_{2k+1})|,|E(S_{n,k})|\}$
for
$n\geq 2k+1$
.
Now, assume that
$G_i$
are two connected components of G with order
$n_i$
and matching number
$\nu (G_i)=a_i>0$
for
$i=1,2$
. Since G is edge-maximal, we have
$n_i\geq 2a_i+1$
; otherwise, we can add one edge e between
$G_1$
and
$G_2$
without increasing the matching number of
$(G_1\cup G_2)+e$
. Elementary calculus gives that
$f_1(n_1,a_1)+f_1(n_2,a_2)<f_1(n_1+n_2,a_1+a_2)$
,
$f_3(2a_1+1,a_1)+f_3(2a_2+1,a_2)<f_3(2a_1+2a_2+1,a_1+a_2)$
, and
$f_1(n_1,a_1)+f_3(2a_2+1,a_2)<f_1(n_1+2a_2+1,a_1+a_2)$
. Also, note that if k is fixed,
$f_1(n,k)$
will increase as n increases. The proof is complete.
In the following, for a graph G, we use
$n_s(G)$
and
$s_r(G)$
to denote the number of s-cliques and the number of
$K_{1,r}$
in G, respectively.
Theorem 4.5 (Luo [Reference Luo20])
Let
$n\geq k\geq 5$
and let
$t=\lfloor \frac {k-1}{2}\rfloor $
. If G is a 2-connected n-vertex graph with circumference less than k, then
$n_s(G)\leq \max \{f_s(n, k,2), f_s(n, k, t)\}$
, where
$f_s(n,k,a):=\binom {k-a}{s}+(n-k+a)\binom {a}{s-1}$
.
Proof By Theorem 3.5, the number of s-cliques in G is weakly-feasible. Thus,
$n_s(G)\leq \max \{f_s(n,k,a):2\leq a\leq t\}$
. As
$f_s(n,k,a)$
is convex,
$n_s(G)\leq \max \{f_s(n,k,2),f_s(n,k,t)\}$
by Theorem 4.1. This proves the theorem.
Similarly, we can prove the following.
Theorem 4.6 (Luo [Reference Luo20])
Let
$n\geq k\geq 4$
and let
$t=\left \lfloor \frac {k}{2}\right \rfloor -1$
. If G is a connected n-vertex graph with
$n_s(G)>\max \{n_s(W_{n,k-1,1}),n_s(W_{n,k-1,t})\}$
, then G has a path of order k.
Theorems 3.6 and 4.2, together with some similar discussions, give us the following result, which is a connected version of Győri–Salia–Tompkins–Zamora’s result [Reference Győri, Salia, Tompkins and Zamora11].
Theorem 4.7 (Győri–Salia–Tompkins–Zamora [Reference Győri, Salia, Tompkins and Zamora11])
Let
$n\geq k\geq 4$
and
$t=\left \lfloor \frac {k}{2}\right \rfloor -1$
. If G is a connected n-vertex graph with
$s_r(G)>\max \{s_r(W_{n,k-1,s}):1\leq s\leq t\}$
, then G has a path of order k.
4.2 Degree power of graphs
To attack a problem of Caro and Yuster, we state the results on the degree power of 2-connected graphs without paths of length at least k first.
Theorem 4.8 Let
$n\geq k\geq 4$
and
$t=\left \lfloor \frac {k}{2}\right \rfloor -1$
. Let G be a connected n-vertex
$P_{k}$
-free graph with the maximum degree power
$\sum _{v\in V(G)}d^p(v),$
where
$p\geq 2$
. Then, G is
$W_{n,k-1,t}$
or
$W_{n,k-1,1}$
.
Proof Note that the p-th degree power is feasible. Given the same settings as Theorem 2.2, by Theorem 2.2, G is a member of
$$ \begin{align*}\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\}.\end{align*} $$
Set
$G=W_{n,k-1,s}$
. Observe that
$$ \begin{align*}\sum_{v\in V(G)}d^p(v)=(n-k+s+1)s^p+s(n-1)^p+(k-2s-1)(k-s-2)^p.\end{align*} $$
Fix n and k. Denote
$\sum _{v\in V(G)}d^p(v)$
by
$D_p(s)$
. We have
$$\begin{align*}\begin{array}{lll} \frac{\mathrm{d} D_p}{\mathrm{d} s}=s^p+p(n-k+s+1)s^{p-1}+(n-1)^p-2(k-s-2)^p-p(k-2s-1)(k-s-2)^{p-1},\\ \frac{\mathrm{d}^{2}D_p}{\mathrm{d}s^2}=ps^{p-1}+p(p-1)(n-k+s+1)s^{p-2}+ps^{p-1}+2p(k-s-2)^{p-1}+2p(k-s-2)^{p-1}\\+p(p-1)(k-2s-1)(k-s-2)^{p-2}. \end{array} \end{align*}$$
Note that
$\frac {\mathrm {d}^{2}D_p}{\mathrm {d}s^{2}}>0$
. Thus,
$D(r)$
is a strictly convex function for the domain, which concludes the result.
When n is sufficiently large, Theorem 4.8 can be improved to the following, attacking a problem of Caro and Yuster.
Theorem 4.9 Let
$k\geq 4$
and
$n\geq 2k$
. Let G be a connected n-vertex
$P_{k}$
-free graph with the maximum degree power
$\sum _{v\in V(G)}d^p(v),$
where
$p\geq 2$
. Then, G is
$W_{n,k-1,t}$
, where
$t=\lfloor \frac {k}{2}\rfloor -1$
.
Proof Let
$G_1$
be
$K_{\left \lfloor \frac {k}{2}\right \rfloor -1}\vee ((n-\lceil \frac {k}{2}\rceil )K_1\cup K_{k-2\lfloor \frac {k}{2}\rfloor +1})$
and let
$G_2$
be
$K_{1}\vee ((n-k+2)K_1\cup K_{k-3})$
. By Theorem 4.8, we only need to prove that the degree power of
$G_1$
is more than the degree power of
$G_2$
(
$k\ne 4,5$
). First, we assume that k is even. We have that
$$ \begin{align} \sum_{v\in V(G_1)}d^p(v)=\left(\frac{k}{2}-1\right)(n-1)^p+(n-\frac{k}{2}+1)\left(\frac{k}{2}-1\right)^p \end{align} $$
and
$$ \begin{align} \sum_{v\in V(G_2)}d^p(v)=n-k+2+(n-1)^p+(k-3)^{p+1}. \end{align} $$
Let
$D(n)= (3)-(4)$
. If
$k=4$
, then we have
$G_1\cong G_2$
. So, we first assume that
$k\geq 6$
. We have
$$ \begin{align*} D(n)&=\left(\frac{k}{2}-2\right)(n-1)^p-(k-3)(k-3)^{p}+(n-\frac{k}{2}+1)\left(\frac{k}{2}-1\right)^p-n+k-2\nonumber\\ &> \left(\frac{k}{2}-2\right)(n-1)^p-(k-3)(k-3)^{p}\nonumber\\ &\geq \left(\frac{k}{2}-2\right)(2k-1)^p-(k-3)(k-3)^{p}\nonumber\\ &=\left(\frac{k}{2}-2\right)2^p\left(k-\frac{1}{2}\right)^p-(k-3)(k-3)^{p}\nonumber\\ &>(k-5)(k-3)^p\nonumber\\ &> 0.\nonumber \end{align*} $$
If k is odd, we have that
$$ \begin{align} \sum_{v\in V(G_1)}d^p(v)=\left(\frac{k-1}{2}-1\right)(n-1)^p+\left(n-\frac{k+1}{2}\right)\left(\frac{k-1}{2}-1\right)^p+2\left(\frac{k-1}{2}\right)^p. \end{align} $$
Now, let
$D(n)=(5)-(4)$
. If
$k=5$
, then we have
$G_1\cong G_2$
. So, we assume that
$k\geq 7$
in what follows. Then,
$$ \begin{align} D(n)&=\left(\frac{k-1}{2}-2\right)(n-1)^p-(k-3)(k-3)^{p}+\left(n-\frac{k+1}{2}\right)\left(\frac{k-1}{2}-1\right)^p\nonumber\\ &\quad +2\left(\frac{k-1}{2}\right)^p-n+k-2\\ &> \left(\frac{k-1}{2}-2\right)(n-1)^p-(k-3)(k-3)^{p}\nonumber\\ &\geq \left(\frac{k-1}{2}-2\right)(2k-1)^p-(k-3)(k-3)^{p}\nonumber\\ &=\left(\frac{k-1}{2}-2\right)2^p\left(k-\frac{1}{2}\right)^p-(k-3)(k-3)^{p}\nonumber\\ &>(k-7)(k-3)^p\nonumber\\ &\geq 0.\nonumber \end{align} $$
Thus,
$ \sum _{v\in V(G_1)}d^p(v)> \sum _{v\in V(G_2)}d^p(v)$
.
Recall that Caro and Yuster have proved the following result.
Theorem 4.10 (Caro and Yuster [Reference Caro and Yuster5])
Let
$k\geq 4$
,
$t=\lfloor \frac {k}{2}\rfloor -1,$
and
$p\geq 2$
. There exists
$n_0(k)$
such that for any integer
$n>n_0(k)$
, if G is an n-vertex
$P_{k}$
-free graph with the maximum degree power
$\sum _{v\in V(G)}d^p(v)$
, then G is
$W_{n,k-1,t}$
. Furthermore,
$W_{n,k-1,t}$
is the unique extremal graph.
Observe that for a connected graph, our extremal graphs, as given in Theorem 4.9, closely align with those identified by Caro and Yuster. We determined
$n_0(k)=2k$
.
Similarly, we can get the following results.
Theorem 4.11 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 degree power
$\sum _{v\in V(G)}d^p(v),$
where
$p\geq 2$
, Then, G is
$W_{n,k,1}$
or
$W_{n,k,t}$
.
4.3 Spectral radius
By Theorems 2.1–2.3 and 3.3, we conclude the following theorem immediately.
Theorem 4.12
-
(i) Let
$n\geq k\geq 5$
and
$t=\left \lfloor \frac {k-1}{2}\right \rfloor $
. If G is a
$2$
-connected n-vertex graph with
$\lambda (G)>\max _{2\leq s\leq t}\{\lambda (W_{n,k,s})\}$
, then G has a cycle of length at least k. In particular,
$\mathrm{spex}_{2-con}(n,\mathcal {C}_{\geq k})=\max _{2\leq s\leq t}\{\lambda (W_{n,k,s})\}$
. -
(ii) Let
$n\geq k\geq 4$
and
$t=\left \lfloor \frac {k}{2}\right \rfloor -1$
. If G is a connected n-vertex graph with
$\lambda (G)>\max _{1\leq s\leq t}\{\lambda (W_{n,k-1,s})\},$
then G has a path of order k. In particular,
$\mathrm{spex}_{con}(n,P_k)=\max _{1\leq s\leq t}\{\lambda (W_{n,k-1,s})\}$
. -
(iii) Let
$n\geq 2k+2$
. If G is a connected n-vertex graph with
$\lambda (G)>\max _{1\leq s\leq k}\{\lambda (W_{n,2k+1,s})\}$
, then G contains an
$M_{k+1}$
. In particular,
$\mathrm{spex}_{con}(n,M_{k+1})=\max _{1\leq s\leq k}\{\lambda (W_{n,2k+1,s})\}$
.
The following result is well-known.
Lemma 7 If G has components
$G_{1}, \dots , G_{r}$
, then
$\lambda (G) = \max \{\lambda (G_{1}), \dots , \lambda (G_{r})\}$
.
The following theorem gives a complete solution to a problem initially posed by Nikiforov [Reference Nikiforov23].
Theorem 4.13 Let
$n\geq k\geq 4$
and
$t=\left \lfloor \frac {k}{2}\right \rfloor -1$
. Let G be an n-vertex
$P_{k}$
-free graph with the maximum spectral radius. Then,
$\lambda (G)=\max \{\lambda (W_{n,k-1,s}),\lambda (K_{k-1}):1\leq s\leq t\}$
. Moreover, the extremal graph G is either
$W_{n, k-1, s}$
for some
$1 \leq s \leq t$
, or has a component isomorphic to
$K_{k-1}$
with
$\lambda (G) = \lambda (K_{k-1})$
.
Proof Let
$G_{1}, \dots , G_{r}$
be the components of G (possibly
$r = 1$
). Without loss of generality and by Lemma 7, assume
$\lambda (G) = \lambda (G_{1})$
and let
$|V(G_1)|=n_1$
.
Case 1:
$n_1 \geq k$
. Since
$G_{1}$
is a connected
$P_k$
-free graph on
$n_1 \geq k$
vertices with the maximum spectral radius, Theorem 2.2 implies that
$G_{1} = W_{n_1, k-1, s_{1}}$
for some
$1 \leq s_{1} \leq t$
. As
$W_{n_1, k-1, s_{1}}$
is a subgraph of
$W_{n, k-1, s_{1}}$
and
$\lambda (G_{1})$
is maximum, we conclude that
$G = G_{1} = W_{n, k-1, s_{1}}$
.
Case 2:
$n_1 \leq k-1$
. In this case,
$G_{1}$
is a
$P_k$
-free graph with at most
$k-1$
vertices. Since
$G_{1} \subseteq K_{k-1}$
, it follows that
$G_{1} = K_{k-1}$
; otherwise,
$\lambda (G_{1}) < \lambda (K_{k-1})$
, contradicting the maximality of
$\lambda (G_{1})$
.
Thus, we conclude that
$$\begin{align*}\lambda(G) = \max\{\lambda(W_{n, k, s}), \lambda(K_{k-1}): 1 \leq s \leq t\}. \end{align*}$$
From the above discussion, when the spectral radius achieves the maximum, the extremal graph G is either
$W_{n, k-1, s}$
for some
$1 \leq s \leq t$
, or contains a component isomorphic to
$K_{k-1}$
.
As we mentioned before, Nikiforov [Reference Nikiforov23] determined the spectral extremal graph for paths when the order of a graph is sufficiently large.
Theorem 4.14 (Nikiforov [Reference Nikiforov23])
Let k be a positive integer. Let G be a graph on
$n\geq 2^{4k}$
vertices. If
$\lambda (G)\geq \lambda (W_{n,k-1,t}),$
where
$t=\lfloor \frac {k}{2}\rfloor -1$
, then G contains a path of order k unless
$G\cong W_{n,k-1,t}$
.
With the help of the following result, we improve Theorem 4.14 from
$n\geq 2^{4k}$
to
$n\geq 3k$
by a different method.
Lemma 8 (Sun–Das [Reference Sun and Das26])
Let G be an n-vertex graph. For any vertex
$v\in V(G)$
, if
$d_G(v)\geq 1$
then
$$ \begin{align*}\lambda^2(G)\leq \lambda^2(G-v)+2d_G(v)-1. \end{align*} $$
Theorem 4.15 Let k be a positive integer. Let G be a graph on
$n\geq 3k$
vertices. If
$\lambda (G)\geq \lambda (W_{n,k-1,t}),$
where
$t=\lfloor \frac {k}{2}\rfloor -1$
, then G contains a path of order k unless
$G\cong W_{n,k-1,t}$
.
Proof Let G be an n-vertex
$P_{k}$
-free graph with the maximum spectral radius. By Theorem 4.13,
$\lambda (G)=\max \{\lambda (W_{n,k-1,s}),\lambda (K_{k-1})\},$
where
$1\leq s\leq t$
. Recall that
$W_{n,k-1,s}$
can be partitioned into three disjoint parts
$A,B,C$
, such that A consists of
$n-k+s+1$
isolated vertices, B is a clique of order s, and C is a clique of order
$k-2s-1$
; moreover,
$(A, B)$
is complete bipartite and
$B\cup C$
is a clique of order
$k-s-1$
, in which
$V(A)\cup V(B)\cup V(C)=V(G)$
. Observe that after deleting
$|V(C)|-1$
vertices in C,
$W_{n,k-1,s}$
is changed into a new graph
$S_{n-k+2s+2,s}$
. (Without loss of generality, assume that the only one vertex in C which has not been deleted is a.) Furthermore, by direct computation, we have
$$ \begin{align*}\lambda(S_{n-k+2s+2,s})\leq \frac{s-1+\sqrt{(s-1)^2+4(n-k+s+2)s}}{2}. \end{align*} $$
By Lemma 8, we obtain
$$ \begin{align*} &\lambda^2(W_{n,k-1,s})\leq \lambda^2(S_{n-k+2s+2,s})+2(e(B\cup C)-e(B\cup \{a\}))-(|V(C)|-1)\\ &=\left(\frac{s-1+\sqrt{(s-1)^2+4(n-k+s+2)s}}{2}\right)^2+2\left(\binom{k-s-1}{2}-\binom{s+1}{2}\right)-(k-2s-2)\\ &:=f(s). \end{align*} $$
Note that when
$t=\frac {k}{2}-1$
and k is even,
$W_{n,k-1,t}=S_{n,\frac {k}{2}-1}$
; when
$t=\frac {k-1}{2}-1$
and k is odd,
$W_{n,k-1,t}=S^+_{n,\frac {k-1}{2}-1}$
, where
$S^+_{n,\frac {k-1}{2}-1}$
is a graph obtained from
$S_{n,\frac {k-1}{2}-1}$
by adding an extra edge in the original independent set of
$n-\frac {k-1}{2}+1$
vertices in
$S_{n,\frac {k-1}{2}-1}$
. Thus, for the first case, we have
$\lambda (W_{n,k-1,t})=\lambda (S_{n,t})$
.
Next, we shall prove that
$f(s)$
is increasing as s is increasing when
$n\geq 3k$
. By computation, we have
$$ \begin{align*} \frac{\mathrm{d}f(s)}{\mathrm{d}s}&=\frac{(s-1)+\sqrt{(s-1)^2+4(n-k+s+2)s}}{2}\left(1+\frac{2n-2k+5s+3}{\sqrt{(s-1)^2+4(n-k+s+2)s}}\right)+4-2k\\ &>\frac{\sqrt{(s-1)^2+4(n-k+s+2)s}}{2}\left(\frac{2n-2k+5s+3}{\sqrt{(s-1)^2+4(n-k+s+2)s}}\right)+4-2k\\ &=n-3k+\frac{5s+3}{2}+4\\ &>n-3k\geq 0. \end{align*} $$
Thus, when
$n\geq 3k$
and k is even,
$\max \{\lambda (W_{n,k-1,s}):1\leq s\leq t\}=\lambda (W_{n,k-1,t})= \lambda (S_{n,t})$
as one can check that when k is even and
$t=\frac {k}{2}-1$
,
$2(e(B\cup C)-e(B\cup \{a\}))-(|V(C)|-1)=0$
. Recall that
$$ \begin{align*}\lambda(S_{n,t})=\frac{(t-1)+\sqrt{(t-1)^2+4(n-t)t}}{2}.\end{align*} $$
For this case,
$\lambda (S_{n,t})>k-2$
when
$n\geq 3k$
and k is even.
Now, we assume that k is odd. For this case,
$t=\frac {k-3}{2}$
. Recall we have
$\lambda (W_{n,k-1,t})> \lambda (S_{n,\frac {k-3}{2}})$
(
$S_{n,\frac {k-3}{2}}$
is obtained from
$W_{n,k-1,t}$
by deleting only one edge) and
$f(s)$
is monotonically increasing for
$1\leq s \leq t$
. Now, we claim
$\lambda ^2(S_{n,\frac {k-3}{2}})> f(t-1)$
. We have
$$ \begin{align*}f(t-1)=\frac{\left(t-2+\sqrt{(t-2)^2+4(n-t-2)(t-1)}\right)^2}{4}+6t+3.\end{align*} $$
On the other hand, we obtain
$$ \begin{align*}\lambda^2(S_{n,\frac{k-3}{2}})=\frac{\left(t-1+\sqrt{(t-1)^2+4(n-t)t}\right)^2}{4}.\end{align*} $$
Then,
$$ \begin{align*} &\frac{\left(t-1+\sqrt{(t-1)^2+4(n-t)t}\right)^2}{4}-\frac{\left(t-2+\sqrt{(t-2)^2+4(n-t-2)(t-1)}\right)^2}{4}-(6t+3)\\ &>\frac{(t-1)^2+(t-1)^2+4(n-t)t}{4}-\frac{(t-2)^2+(t-2)^2+4(n-t-2)(t-1)}{4}-(6t+3)\\ &=\frac{4n+8t-14}{4}-(6t+3)\\ &=n-4t-\frac{13}{2}=n-2k-\frac{1}{2}>0. \end{align*} $$
Thus,
$\max \{\lambda (W_{n,k-1,s}):1\leq s\leq t\}=\lambda (W_{n,k-1,t})$
. Meanwhile, we have
$$ \begin{align*}\lambda(S_{n,\frac{k-3}{2}})=\frac{1}{2}\cdot \left(t-1+\sqrt{(t-1)^2+4(n-t)t}\right)>2t+1\end{align*} $$
for
$n\geq 3t+6$
. Thus, if
$\lambda (G)\geq \lambda (W_{n,k-1,t}),$
where
$t=\lfloor \frac {k}{2}\rfloor -1$
, then G contains a path of order k unless
$G\cong W_{n,k-1,t}$
. The proof is complete.
By a similar proof as that of Theorem 4.13, we can get the following.
Theorem 4.16 Let G be an n-vertex
$M_{k+1}$
-free graph with the maximum spectral radius, where
$n\geq 2k+1$
. Then,
$\lambda (G)= \max \{\lambda (W_{n, 2k+1, s}), \lambda (K_{2k+1}): 1 \leq s \leq k\}$
. Moreover, the extremal graph G is either
$W_{n, 2k+1, s}$
for some
$1 \leq s \leq k$
, or has a component isomorphic to
$K_{2k+1}$
with
$\lambda (G) = \lambda (K_{2k+1})$
.
4.4 Signless Laplacian spectral radius
For the signless Laplacian spectral radius version, we also have the following theorems. (We omit the results related to matching here.)
Theorem 4.17
-
(i) Let
$n\geq k\geq 5$
and
$t=\left \lfloor \frac {k-1}{2}\right \rfloor $
. If G is a 2-connected n-vertex graph with
$q(G)>\max _{2\leq s\leq t}\{q(W_{n,k,s})\}$
, then G has a cycle of length at least k. In particular,
$\mathrm{sspex}_{2-con}(n,\mathcal {C}_{\geq k})=\max _{2\leq s\leq t}\{q(W_{n,k,s})\}$
. -
(ii) Let
$n\geq k\geq 4$
and let
$t=\left \lfloor \frac {k}{2}\right \rfloor -1$
. If G is a connected n-vertex graph with
$q(G)>\max _{1\leq s\leq t}\{q(W_{n,k-1,s})\},$
then G has a path of order k. In particular,
$\mathrm{sspex}_{con}(n,P_k)=\max _{1\leq s\leq t}\{q(W_{n,k-1,s})\}.$
Theorem 4.18 Let
$n\geq k\geq 4$
and
$t=\left \lfloor \frac {k}{2}\right \rfloor -1$
. Let G be an n-vertex
$P_{k}$
-free graph with the maximum signless Laplacian spectral radius. Then,
$q(G)=\max \{q(W_{n,k-1,s}),q(K_{k-1}): 1\leq s\leq t\}$
.
Proof Let
$G_i$
be a connected graph of order
$n_i(\geq k)$
with maximum spectral radius for
$i=1,2$
. By Theorem 4.17,
$G_1\cong W_{n_1,k-1,s_i}$
and
$G_2\cong W_{n_2,k-1,s_j}$
for some
$1\leq s_i\leq t$
and
$1\leq s_j\leq t$
. We assume
$n_1<n_2$
. Observe that
$W_{n_1,k-1,s_i}$
is a proper subgraph of
$W_{n_2,k-1,s_i}$
and
$q(W_{n_2,k-1,s_j})\geq q(W_{n_2,k-1,s_i})$
. Thus,
$q(W_{n_2,k-1,s_j})> q(W_{n_1,k-1,s_i})$
, and it follows that
$q(G_1)<q(G_2)$
. On the other hand,
$q(G)\geq q(K_{k-1})=2k-4$
since
$n\geq k$
. So, if
$q(W_{n_2,k-1,s_i})\geq 2k-4$
for some
$1\leq s_i\leq t $
, then
$q(G)=\max \{q(W_{n,k-1,s})\},$
where
$1\leq s\leq t$
. If
$q(W_{n_2,k-1,s_i})< 2k-4$
, we have that
$q(G)=2k-4$
as the size of a clique in a
$P_{k}$
-free graph is at most
$k-1$
. This proves the theorem.
5 Proofs of main theorems
Before providing proofs of our main theorems, we prove some useful lemmas.
5.1 Kelmans operation and related lemmas
We say that a pair of adjacent vertices x and y is a bad pair if
$N[x]\backslash N[y]\neq \emptyset $
and
$N[y]\backslash N[x]\neq \emptyset $
.
Definition 4 Let G be a graph. We say that
$G'$
is a threshold graph of G if
$G'$
can be obtained by starting with G and repeatedly applying KO to bad pairs in the current graph until none remain.
Note that after each KO, the degree sequence is increasing with respect to the lexicographical ordering, so Definition 4 is well-defined. Clearly, if G is connected, then the threshold graphs
$G'$
remain connected. Let
$S_{n,t}$
denote a graph formed by joining a clique of order t with an independent set of order
$n-t$
. Note that the maximum clique in
$S_{n,t}$
has an order of
$t+1$
. From the subsequent lemma, we can see that the threshold graph is well-defined.
Lemma 9 Let G be a connected graph and
$G'$
be a threshold graph of G. Then, the following statements hold:
-
(i) For any
$xy\in E(G')$
,
$N[x]\subseteq N[y]$
or
$N[y]\subseteq N[x]$
. -
(ii) Any two maximal cliques in
$G'$
share at least one common vertex. -
(iii) For any two maximal cliques X and Y, there are no edges between
$X-Y$
and
$Y-X$
. -
(iv) Let S be a maximum clique of
$G'$
. Then, for any two maximal cliques X and Y, we have
$X\cap S\subseteq Y\cap S$
or
$Y\cap S\subseteq X\cap S$
. Furthermore,
$X\cap Y\subseteq S$
.
Proof
-
(i) It follows from the definition of a threshold graph. (For details, see Lemma 3.1(1) in [Reference Li and Ning16].)
-
(ii) Suppose that X and Y are two disjoint maximal cliques in
$G'$
. Then, pick one vertex x from X and one vertex y from Y. If
$xy\in E(G')$
, we have
$X\cap Y\ne \emptyset $
since
$x,y$
is not a bad pair. So, we may assume that there is no edge between X and Y. As
$G'$
is connected, there is a shortest path between x and y. Observe that the path length is at most two, and say the middle vertex is a. Now, either
$\{a\}\cup X (\{a\}\cup Y)$
is a larger clique or there is an edge between X and Y, a contradiction. -
(iii) We prove this by contradiction. Suppose there are two maximal cliques X and Y such that we can find a vertex
$x\in X-Y$
and a vertex
$y\in Y-X$
satisfying
$xy\in E(G')$
. Then by (i), suppose, without loss of generality,
$N[x]\subseteq N[y]$
, we have
$X\subseteq N(y)$
, a contradiction to the fact that X is a maximal clique.
For (iv), it is not hard to check by (iii).
Using the definition of KO, we can conclude the following technical result.
Lemma 10 Let G be a connected graph and
$G'$
be a threshold graph of G. Let s and p denote the orders of the maximum clique and the second maximum clique of
$G'$
, respectively. Then after a series of EKO,
$G'$
can become a new graph
$G"$
, which is a subgraph of
$K_{p-1}\vee (K_{s-p+1}\cup (n-s)K_1)$
. Furthermore, if
$G"=K_{p-1}\vee (K_{s-p+1}\cup (n-s)K_1)$
, then
$G'=K_{p-1}\vee (K_{s-p+1}\cup (n-s)K_1)$
.
Proof Let X be a maximum clique of
$G'$
with
$|X|=s$
. By Lemma 9(iv), there is a maximal clique
$X'$
such that for any maximal clique Z,
$Z\cap X\subseteq X'\cap X$
, we denote
$X'\cap X$
by I. Now, let
$Y_1,Y_2,\ldots ,Y_{\ell }$
be all maximal cliques of
$G'$
other than X. Notice that
$V(\bigcup _{1\leq i\leq \ell }Y_i\cup X)=V(G)$
and for any
$1\leq i\leq \ell $
,
$V(Y_i\cap X)\neq \emptyset $
and
$Y_i\cap X\subseteq I$
. Without loss of generality, assume that
$Y_1$
is a second maximum clique with
$|Y_1|=p$
. We have
$|Y_1|>|I|$
.
Let
$T=X\cap Y_1$
and
$|T|=t$
. Then,
$T\subseteq I$
and let
$V(Y_1-T)=B_1=\{y^1_1,y^1_2,\ldots , y^1_{p-t}\}$
. We choose
$A_1:=\{x^1_1,x^1_2,\ldots , x^1_{p-t-1}\}$
from
$X-T$
such that
$V(I-T)\subseteq A_1$
. By Lemma 9(iii), there are no edges between
$X-T$
and
$Y_1-T$
. Now, let
$G^1_1=G'$
and
$G^1_{i+1}=G^1_i[y^1_i\to x^1_i]$
(EKO) for
$1\leq i\leq p-t-1$
. In
$G^1_{p-t}$
,
$Y_1-T$
turns into an empty graph (a graph has no edge), and
$G^1_{p-t}[V(X\cup Y_1)]$
is a subgraph of
$K_{p-1}\vee (K_{s-p+1}\cup (p-t)K_1)$
, where
$G^1_{p-t}[A_1\cup V(T)]\cong K_{p-1}$
,
$G^1_{p-t}[V(Y_1-T)]\cong (p-t)K_1$
, and
$G^1_{p-t}[V(X)\backslash (A_1\cup V(T))]\cong K_{s-p+1}$
.
Now, let
$G^2=G^1_{p-t}$
. Note that
$G^2$
is a threshold graph of
$G-V(Y_1-T)$
; otherwise,
$G'$
is not a threshold graph of G. Now, consider
$Y_2$
. Let
$B_2=V(Y_2-I)=\{y^2_1,y^2_2,\dots ,y^2_{|Y_2-I|}\}$
. Now, pick
$|Y_2-I|-1$
vertices from
$A_1\cup (I-Y_2),$
which are not contained in
$Y_2\cap I$
to make up
$A_2$
. Let
$G^2_1=G^2$
and
$G^2_{i+1}=G^2_i[y^2_i\to x^2_i]$
(EKO) for
$1\leq i\leq |Y_2-I|-1$
. In
$G^2_{|Y_2-I|}$
,
$Y_2-I$
turns into an empty graph,
$G^2_{|Y_2-I|}[V(X\cup Y_1\cup Y_2)]$
is a subgraph of
$K_{p-1}\vee (K_{s-p+1}\cup (|Y_1\cup Y_2-I|)K_1)$
. When it comes to
$Y_i$
, let
$G^i=G^{i-1}_{|Y_{i-1}-I|}$
and
$B_i=V(Y_i-I)=\{y^i_1,y^i_2,\dots ,y^i_{|Y_i-I|}\}$
. Pick
$|Y_i-I|-1$
vertices from
$A_1\cup (I-Y_i),$
which are not contained in
$Y_i\cap I$
to make up
$A_i$
. Let
$G^i_1=G^i$
and
$G^i_{j+1}=G^i_j[y^i_j\to x^i_j]$
(EKO) for
$1\leq j\leq |Y_i-I|-1$
. In
$G^i_{|Y_i-I|}$
,
$Y_i-I$
turns into an empty graph,
$G^i_{|Y_i-I|}[V(X\cup Y_1\cup Y_2\cup \dots \cup Y_i)]$
is a subgraph of
$K_{p-1}\vee (K_{s-p+1}\cup (|(Y_1\cup Y_2\cup \dots \cup Y_i)-I|)K_1)$
. Keep doing the process until we get
$G^{\ell }$
. We have that
$G^\ell $
is a subgraph of
$K_{p-1}\vee (K_{s-p+1}\cup (|(Y_1\cup Y_2\cup \dots \cup Y_\ell )-I|)K_1)=K_{p-1}\vee (K_{s-p+1}\cup (n-s)K_1)$
.
If we do at least one EKO, then there exists
$1\leq i\leq \ell $
such that there is no edge between
$y^i_1$
and
$A_1\backslash V(Y_i\cap I)$
. Hence,
$G"$
is a proper subgraph of
$K_{p-1}\vee (K_{s-p+1}\cup (n-s)K_1)$
. If
$G"=K_{p-1}\vee (K_{s-p+1}\cup (n-s)K_1)$
, then by the arguments above, we did not do any EKO on
$G'$
, and so
$G'=K_{p-1}\vee (K_{s-p+1}\cup (n-s)K_1)$
.
Note that
$K_{p-1}\vee (K_{s-p+1}\cup (n-s)K_1)$
is a subgraph of
$S_{n,s-1}$
. The following lemma can be deduced directly.
Lemma 11 Let G be a connected graph and
$G'$
be a threshold graph of G. Let X be a maximum clique of
$G'$
with
$|X|=s$
. Then,
$G'=S_{n,s-1}$
or after a series of EKO,
$G'$
becomes a proper subgraph of
$S_{n,s-1}$
.
To prove some of our main results, we may require the assistance of the following lemmas.
Lemma 12 (Gao and Hou [Reference Gao and Hou10])
Let G be a graph and
$uv\in E(G)$
, and
$G':=G[u\rightarrow v]$
. Then,
$c(G')\leq c(G)$
.
Lemma 13 Let G be a graph and
$uv\in E(G)$
, and
$G':=G[u\rightarrow v]$
. If there is a path of order k in
$G'$
, then there is a path of order at least k in G.
Proof Let
$P'=x_1x_2\dots x_k$
be a path of order k in
$G'$
. If
$P'$
does not contain an edge
$va,$
where
$a\in N_G(u)\backslash N_G(v)$
, then
$P'$
is also a path in G, we are done. So, we may assume that
$P'$
contains such an edge
$va$
. If
$u\notin P'$
, then we can replace
$va$
with
$au$
and
$uv$
of
$P'$
in G to get a longer path, and we are done. If
$P'$
does not contain an edge
$vb$
where
$b\in N_G(v)\backslash N_G(u)$
, we can easily swap u and v in
$P'$
to get a new path P in G. Observe that
$|P|=|P'|$
, we are done. So, we assume such an edge
$vb$
exists in
$P'$
. Without loss of generality, we assume
$u=x_i$
and
$v=x_j$
, with
$i<j$
. Now, we complete this proof by considering the following two cases:
Case 1:
$d_{P'}(x_i)=1$
. Let
$P=P'-\{ax_j\}+\{ax_i\}$
when
$a=x_{j+1}$
and
$P=P'-\{au_j\}+\{x_jx_i\}$
when
$a=x_{j-1}$
, then P is a path of the same order as
$P'$
in G.
Case 2:
$d_{P'}(x_i)=2$
. First, we assume that
$x_i\ne b$
. Note that
$x_{i-1}, x_{i+1}\in N(x_i)\cap N(x_j)$
. Let
$P=P'-\{ax_j, x_ix_{i-1}\}+\{ax_i, x_jx_{i-1}\}$
when
$a=x_{j+1}$
and
$P=P'-\{ax_j, x_ix_{i-1}\}+\{x_jx_i, ax_{i-1}\}$
when
$a=x_{j-1}$
, then P is a path of the same order as
$P'$
in G. If
$x_i=b$
, so
$x_j=x_{i+1}$
. Then, let
$P=P'-\{ax_j, x_ix_{i-1}\}+\{ax_i, x_jx_{i-1}\}$
and P is a path of the same order as
$P'$
in G.
Lemma 14 Let G be a graph and
$uv\in E(G)$
, and
$G':=G[u\rightarrow v]$
. Then,
$\nu (G')\leq \nu (G)$
.
Proof Let
$M'$
be a maximum matching in
$G'$
. If
$M'\cap (E(G')\backslash E(G))=\emptyset $
, then
$M'$
is a matching in G, we are done. So, we may assume that there is an edge
$e\in M'$
incident to v, say
$e=va$
, which is not in
$E(G)$
. Then, if there is no edge incident to u in
$M'$
,
$M'\backslash \{va\}\cup \{ua\}$
is a matching in G; if there is an edge
$ub\in M'$
,
$M'\backslash \{va,ub\}\cup \{ua,vb\}$
is a matching in G, we are done.
5.2 Kopylov’s operation and related lemmas
Our proofs need Kopylov’s operation along with some lemmas presented below.
Definition 5 (
$\alpha $
-disintegration of a graph [Reference Kopylov13])
Let G be a graph and
$\alpha $
be a natural number. Delete all vertices of degree at most
$\alpha $
from G; for the resulting graph
$G'$
, we again delete all vertices of degree at most
$ \alpha $
from
$G'$
. We keep running this process until we finally get a graph, denoted by
$H(G;\alpha )$
, such that all vertices are of degree larger than
$\alpha $
.
Lemma 15 (Kopylov [Reference Kopylov13])
Let G be a 2-connected n-vertex graph with a path P of m edges with endpoints x and y. Then, G contains a cycle of length at least
$\min \{m+1,d_P(x)+d_P(y)\}$
.
Lemma 16 Let
$\Gamma $
be a connected n-vertex graph with two vertex-disjoint paths, say
$F=\{P_1,P_2\}$
, in which
$|V(P_1)|+|V(P_2)|=p$
and
$x,y$
are end-vertices of
$P_1,P_2$
, respectively. For
$v\in V(G)$
, let
$d_F(v)=|N(v)\cap (V(P_1)\cup V(P_2))|$
. Then,
$\Gamma $
contains a path of order at least
$\min \{p,d_F(x)+d_F(y)+1\}$
.
Proof Add a new vertex z and let
$G:=\Gamma \vee \{z\}$
. Since
$\Gamma $
is connected, G is
$2$
-connected. Let
$x'$
be the other end-vertex of
$P_1$
and
$y'$
be the other end-vertex of
$P_2$
. Let
$P:=P_1x'zy'P_2$
. Then, P is a path of order
$p+1$
. Moreover,
$d_{P}(x)=|N_{G}(x)\cap V(P)|=d_F(x)+1$
and
$d_P(y)=d_F(y)+1$
. By Lemma 15, there is a cycle of length at least
$\min \{p+1,d_F(x)+d_F(y)+2\}$
, say C. If C contains the vertex z, then
$P'=C-\{z\}$
is a path in
$\Gamma $
with order at least
$\min \{p,d_F(x)+d_F(y)+1\}$
. If C does not contain z, then deleting any edge of C gives a path in
$\Gamma $
with order at least
$\min \{p+1,d_F(x)+d_F(y)+2\}$
. This proves the lemma.
5.3 Proofs of Theorems 2.1–2.3
Now, we are ready to provide the proofs.
Proof of Theorem 2.1
We prove the theorem by contradiction. Let G be an n-vertex
$2$
-connected graph containing no
$\mathcal {C}_{\geq k}$
with the maximum
$\mathcal {P}(G)$
but
$G\notin \mathcal {G}^1_{n,k}$
. Since
$\mathcal {P}(G)$
is maximum, by Property (II) in the definition of feasible, G has the maximal number of edges. So, adding any new edge (i.e., joining any two non-adjacent vertices) will increase the value of
$\mathcal {P}(G)$
. Thus, G is edge-maximal, and adding any new edge creates a cycle of length at least k in the resulting graph. We state it in another form.
Claim 1 For any two non-adjacent vertices
$x,y\in V(G)$
, there is a path with
$x,y$
as two end-vertices in G of order at least k.
For any two adjacent vertices
$x,y\in V(G)$
, if neither
$N_G[x]\subset N_G[y]$
nor
$N_G[y]\subset N_G[x]$
, we use the KO to get a new graph
$G_{xy}=G[x\rightarrow y]$
or
$G_{yx}=G[y\rightarrow x]$
. By Property (I), we have
$\mathcal {P}(G_{xy})\geq \mathcal {P}(G)$
and
$\mathcal {P}(G_{yx})\geq \mathcal {P}(G)$
.
After a series of KO, the procedure will stop and result in a threshold graph, denoted by
$\Gamma $
. In the following, let
$G:=G_0, G_1, G_2,\dots , G_h:=\Gamma $
be a sequence of graphs, such that
$G_{i+1}=G_i[u_i\to v_i]$
, where
$u_iv_i\in E(G_i)$
and
$G_h$
is a threshold graph of G. Hence,
$\mathcal {P}(\Gamma )\geq \mathcal {P}(G)$
.
Claim 2 If
$\Gamma \in \mathcal {G}^1_{n,k}$
, then
$G\cong \Gamma $
.
Proof Suppose
$\Gamma =W_{n,k,s}=K_{s}\vee ((n-k+s)K_1\cup K_{k-2s})$
, where
$2\leq s\leq t$
. We partition
$V(W_{n,k-1,s})$
into three disjoint parts
$A,B,C$
, such that A consists of
$n-k+s$
isolated vertices, B is a clique of order s, and C is a clique of order
$k-2s$
; moreover,
$(A, B)$
is complete bipartite and
$B\cup C$
is a clique of order
$k-s$
.
Now, we consider
$G_{h-1}$
. Suppose
$G_{h-1}\not \cong \Gamma $
. Recall that
$\Gamma =G_{h-1}[u_{h-1}\to v_{h-1}]$
. For simplicity, we denote
$u_{h-1}$
by u and
$v_{h-1}$
by v. By the definition of KO, we have
$N_\Gamma (u)\subset N_\Gamma (v)$
and
$uv\in E(\Gamma )$
. Notice that
$N_{\Gamma }(u)=N_{\Gamma }(v)$
when
$u,v\in B$
or
$u,v\in C$
. Thus,
$v\in B$
and
$u\in A\cup C$
. Suppose
$v\in B$
and
$u\in A$
. Then,
$N_{G_{h-1}}(u)\cap N_{G_{h-1}}(v)=B-\{v\}$
,
$A\cup C\subset N_{G_{h-1}}(u)\cup N_{G_{h-1}}(v)$
,
$N_{G_{h-1}}(u)\cap (A\cup C)\neq \emptyset ,$
and
$N_{G_{h-1}}(v)\cap (A\cup C)\neq \emptyset $
. If
$C\subset N_{G_{h-1}}(u)$
, we switch u and v as
$G[u\to v]\cong G[v\to u]$
. So, we can always assume that there is a vertex
$c\in C$
such that
$vc\in G_{h-1}$
. If
$N_{G_{h-1}}(u)\cap A \neq \emptyset $
, then let
$a\in A$
and
$ua\in G_{h-1}$
. Note that we can always find a Hamiltonian path
$P_1$
ending at v and b in
$G_{h-1}[C\cup \{v,b\}],$
where
$b\in B$
. As
$A-\{u\}$
and
$B-\{b,v\}$
is complete bipartite, there is a path
$P_2$
containing all vertices in
$G_{h-1}[B-\{b,v\}]$
and ending at b and
$a,$
which contains
$s-2$
vertices from A. Then, we get a cycle of length k by combining
$P_1$
,
$P_2$
and
$auv$
in
$G_{h-1}$
, a contradiction. If
$ud\in G_{h-1}$
for some
$d\in C$
, we can obtain a desired cycle by a similar argument. Suppose that
$v\in B$
and
$u\in C$
. Then,
$N_{G_{h-1}}(u)\cap N_{G_{h-1}}(v)=B\cup C-\{u, v\}$
,
$A\subset N_{G_{h-1}}(u)\cup N_{G_{h-1}}(v)$
,
$N_{G_{h-1}}(u)\cap A\neq \emptyset ,$
and
$N_{G_{h-1}}(v)\cap A\neq \emptyset $
. Let
$a\in N_{G_{h-1}}(v)\cap A$
and
$b\in N_{G_{h-1}}(u)\cap A $
. Note that
$a\neq b$
. Similarly to above, there is a path
$P_2$
containing all vertices in B and ending at b and
$v,$
which contains s vertices from A, and we can always find a Hamiltonian path
$P_1$
ending at v and u in
$C\cup \{v\}$
. Then, we get a cycle of length k by combining
$P_1$
,
$P_2$
and
$bu$
in
$G_{h-1}$
, a contradiction.
So
$G_{h-1}\cong \Gamma $
. Hence,
$G\cong G_1\cong \cdots \cong G_{h-1}\cong \Gamma $
.
Claim 3 Recall that
$t=\left \lfloor \frac {k-1}{2}\right \rfloor $
. Let
$H=H(\Gamma ;t)$
. Then, H is not empty.
Proof Suppose to the contrary that
$H=\emptyset $
. Choose a maximum clique in
$\Gamma $
, and denote it by X.
Let
$|X|=s$
. Recall that
$\Gamma [X]=K_s$
. Since
$H=\emptyset $
,
$s\leq t+1$
. Indeed, if
$s\geq t+2$
, then there is a
$K_{t+2}$
-clique in
$\Gamma $
. After all t-disintegrations of
$\Gamma $
, the
$K_{t+2}$
-clique is still a
$K_{t+2}$
-clique in H, contradicting the fact that
$H=\emptyset $
. This shows that
$s\leq t+1$
. Assume after applying a series of EKO to
$\Gamma $
,
$\Gamma $
becomes a proper subgraph of
$S_{n, s-1}$
. Notice that the largest cycle in
$S_{n, s-1}$
is of length at most
$2s-2$
and
$2s-2\leq 2t\leq k-1$
. Then, there is a contradiction to the fact that
$\mathcal {P}(G)$
is maximum since
$S_{n, s-1}$
is
$\mathcal {C}_{\geq k}$
-free graph. Thus, by Claim 2 and Lemma 11,
$G=S_{n, s-1}=W_{n,k-1,s-1}$
, which is a contradiction to the assumption that
$G\notin \mathcal {G}^1_{n,k}$
.
Claim 4 H is a clique.
Proof We shall show that H is a clique. Suppose
$x,y \in V(H)$
are not adjacent in H. Then, x and y are not adjacent in
$\Gamma $
either. As G is edge-maximal,
$|E(G)|=|E(\Gamma )|$
and
$\mathcal {P}(\Gamma +xy)>\mathcal {P}(\Gamma )$
, we know that
$\Gamma +xy$
contains a cycle of length at least k. Thus, there is an
$(x,y)$
-path of length at least
$k-1$
in
$\Gamma $
.
By Claim 2,
$\Gamma $
is
$2$
-connected. Without loss of generality, we choose
$x,y\in V(H)$
with
$xy\notin E(H)$
such that the length of a longest
$(x,y)$
-path is the maximum among all possible pairs
$x,y$
, say P, with these two vertices as end-vertices in
$\Gamma $
. We claim
$N_H(x) \subseteq V(P)$
and
$N_H(y) \subseteq V(P)$
. Suppose
$z \in N_H(x) $
and
$z \not \in V(P)$
. If
$yz \in E(G)$
, then we get a cycle of order at least
$k+1$
, a contradiction. If
$y,z$
are nonadjacent, then we get two new vertices
$y,z$
such that there is a longer path
$yz+P$
with these two vertices as end-vertices, also a contradiction. The same argument also holds for y.
By Lemma 15, we get a cycle of length at least
$\min \{k-1+1,d_H(x)+d_H(y) \}\geq \min \{k,2(t+1)\} \geq k$
in
$\Gamma $
. According to Lemma 12, there is a cycle of length at least k in G as well, a contradiction. This proves the claim.
Claim 5
H is a clique with the maximum size in
$\Gamma $
.
Proof Suppose that there exists another clique, say
$H'$
in
$\Gamma $
, such that
$|H'|>|H|$
. Then, for any vertex
$v\in V(H')$
,
$d_{H'}(v)\geq |H'|-1\geq |H|\geq t+2$
. As
$H'$
is a clique in
$\Gamma $
, any vertex in
$H'$
cannot be deleted in
$H(\Gamma ;t)$
, and hence,
$H'\subseteq H$
, contradicting the fact that
$|H'|>|H|$
. This proves the claim.
Claim 6 Let
$r=|V(H)|$
. Then,
$t+2\leq r\leq k-2$
, and so
$2\leq k-r\leq t.$
Proof As
$H=H(\Gamma ;t)$
is a clique,
$r \geq t+2$
. We claim that
$r\leq k-2$
. If
$r\geq k$
, then there is a cycle of length at least k, a contradiction. Thus, we may assume that
$r=k-1$
. By Claim 2,
$\Gamma $
is
$2$
-connected, so there is a cycle of length at least k in
$\Gamma $
, as for each vertex not in H, say a, there are two paths between a and H that are disjoint except at a. Then,
$c(G)\geq k$
by Lemma 12, a contradiction. So,
$k-r\leq k-t-2=k-\left \lfloor \frac {k-1}{2}\right \rfloor -2\leq \left \lfloor \frac {k-1}{2}\right \rfloor =t$
. This proves the claim.
Claim 7 Let
$H'=H(\Gamma ;k-r)$
. Then,
$H \neq H'$
.
Proof Suppose
$H=H'$
. Note that each vertex from
$V(G)\setminus V(H')$
has degree at most
$k-r$
at the time of its deletion. So the size of the second largest maximal clique is at most
$k-r+1$
. By Lemma 10 and Claim 2, after applying a series of EKO to
$\Gamma $
,
$\Gamma $
becomes a proper subgraph of
$K_{k-r}\vee ((n-r)K_1\cup K_{2r-k})\in \mathcal {G}^1_{n,k}$
or
$G=\Gamma =K_{k-r}\vee ((n-r)K_1\cup K_{2r-k})$
, then
$\mathcal {P}(\Gamma )< \mathcal {P}(K_{k-r}\vee ((n-r)K_1\cup K_{2r-k})),$
or
$G\in \mathcal {G}^1_{n,k}$
, a contradiction. This proves the claim.
Claim 8 G contains a cycle of length at least k.
Thus,
$V(H) \subset V(H')$
and
$H \neq H'$
. We select
$x \in V(H) $
and
$y \in V(H') \setminus V(H)$
such that x and y are nonadjacent and the longest path between them in
$\Gamma $
contains the largest number of edges among all such pairs. Let P be a longest path between x and y, we can assert that the length of P is at least
$k-1$
since otherwise
$\mathcal {P}(\Gamma +xy)>\mathcal {P}(\Gamma )$
. Now, we claim
$N_H(x) \subseteq V(P)$
and
$N_{H'}(y) \subseteq V(P)$
. By Claim 2,
$\Gamma $
is
$2$
-connected. Then, Lemma 15 implies that there is a cycle in
$\Gamma $
with length at least
$\min \{k, d_P(x)+d_P(y)\} \geq \min \{k,r-1+k-r+1\}=k$
. By Lemma 12, there is a cycle of length at least k in G. We get a contradiction.
A basic fact in graph theory is the following: A graph G contains a path of order k if and only if
$G\vee K_1$
contains a cycle of order at least
$k+1$
. However, we cannot deduce Theorem 2.2 from Theorem 2.1 with the aid of this idea. Some further discussions can be found in our last section.
Proof of Theorem 2.2
We prove the theorem by contradiction. Let G be an n-vertex connected graph containing no
$P_{k}$
with the maximum
$\mathcal {P}(G)$
but
$G\notin \mathcal {G}^2_{n,k}$
. Since
$\mathcal {P}(G)$
is maximum, by Property (II), G has the maximal number of edges. Adding any new edge (i.e., joining any two non-adjacent vertices) will increase the value of
$\mathcal {P}(G)$
. Thus, G is edge-maximal. We have the following.
Claim 1 For any two non-adjacent vertices
$x,y\in V(G)$
, there are two vertex-disjoint paths
$P_1=P(x)$
and
$P_2=P(y)$
, in which one has x as an end-vertex and the other has y as an end-vertex, and
$v(P_1)+v(P_2)\geq k$
.
For any two adjacent vertices
$x,y\in V(G)$
, if neither
$N_G(x)\subset N_G(y)$
nor
$N_G(y)\subset N_G(x)$
, we use the KO to get a new graph
$G_{xy}=G[x\rightarrow y]$
or
$G_{yx}=G[y\rightarrow x]$
. By Property (I), we have
$\mathcal {P}(G_{xy})\geq \mathcal {P}(G)$
and
$\mathcal {P}(G_{yx})\geq \mathcal {P}(G)$
.
After a series of KO, the procedure will stop and result in a threshold graph, denoted by
$\Gamma $
. In the following, let
$G:=G_0, G_1, G_2,\dots , G_h:=\Gamma $
be a sequence of graphs, such that
$G_{i+1}=G_i[u_i\to v_i]$
, where
$u_iv_i\in E(G_i)$
and
$G_h$
is a threshold graph of G. Hence,
$\mathcal {P}(\Gamma )\geq \mathcal {P}(G)$
.
Claim 2 If
$\Gamma \in \mathcal {G}^2_{n,k}$
, then
$G\cong \Gamma $
.
Proof Suppose
$\Gamma =W_{n,k-1,s}=K_{s}\vee ((n-k+s+1)K_1\cup K_{k-2s-1})$
, where
$1\leq s\leq t$
. We partition
$V(W_{n,k-1,s})$
into three disjoint parts
$A,B,C$
, such that A consists of
$n-k+s+1$
isolated vertices, B is a clique of order s, and C is a clique of order
$k-2s-1$
; moreover,
$(A, B)$
is complete bipartite and
$B\cup C$
is a clique of order
$k-s-1$
.
Now, we consider
$G_{h-1}$
. Recall that
$\Gamma =G_{h-1}[u_{h-1}\to v_{h-1}]$
. For simplicity, we denote
$u_{h-1}$
by u and
$v_{h-1}$
by v. By the definition of KO, we have
$N_\Gamma (u)\subset N_\Gamma (v)$
and
$uv\in E(\Gamma )$
. Notice that
$N_{\Gamma }(u)=N_{\Gamma }(v)$
when
$u,v\in B$
or
$u,v\in C$
. Thus,
$v\in B$
and
$u\in A\cup C$
. Suppose
$G_{h-1}\not \cong \Gamma $
. Then,
$N_{G_{h-1}}(u)\cap (A\cup C)\neq \emptyset $
,
$N_{G_{h-1}}(v)\cap (A\cup C)\neq \emptyset ,$
and
$A\cup C\subset N_{G_{h-1}}(u)\cup N_{G_{h-1}}(v)$
.
Suppose that
$v\in B$
and
$u\in A$
. We have
$B-v \subseteq N_{G_{h-1}}(u)\cap N_{G_{h-1}}(v)$
. Suppose
$N_{G_{h-1}}(v)\cap C=\emptyset $
or
$N_{G_{h-1}}(u)\cap A=\emptyset $
. Let
$a\in N_{G_{h-1}}(v)\cap A$
and
$b\in N_{G_{h-1}}(u)\cap C$
. Let
$G_{u,v,a}$
be the graph obtained by deleting the three vertices
$u,v,a$
from
$G_{h-1}$
. Since
$G_{u,v,a}\cong K_{s-1}\vee ((n-k+s-1)K_1\cup K_{k-2s-1})$
, there is a path P of order
$k-3$
ending at b in
$G_{u,v,a}$
. We can extend P from b by adding
$bu$
,
$uv$
, and
$va$
such that the order of the new path is now k, a contradiction. The case
$N_{G_{h-1}}(u)\cap C=\emptyset $
or
$N_{G_{h-1}}(v)\cap A=\emptyset $
is similar, now consider
$N_{G_{h-1}}(x)\cap A\neq \emptyset $
and
$N_{G_{h-1}}(x)\cap C\neq \emptyset $
, where
$x\in \{u,v\}$
. Without loss of generality, assume
$|N_{G_{h-1}}(u)\cap A|\geq 2$
. Let
$a\in N_{G_{h-1}}(v)\cap A$
and
$b\in N_{G_{h-1}}(v)\cap C$
. Let
$G_{v}$
be the graph obtained by deleting v from
$G_{h-1}$
. Notice that there are two disjoint paths
$P_1$
and
$P_2$
in
$G_{v}$
, where
$P_1$
is a path of order
$2s$
ending at a and
$P_2$
is a path of order
$k-2s-1$
ending at b. We can extend
$P_1$
and
$P_2$
from a and b, respectively, by adding
$av$
and
$vb$
such that the order of the new path is k, a contradiction.
Suppose that
$v\in B$
and
$u\in C$
. We have
$(B\cup C)-\{u,v\} \subseteq N_{G_{h-1}}(u)\cap N_{G_{h-1}}(v)$
. Since
$G_{h-1}\not \cong \Gamma $
,
$N_{G_{h-1}}(u)\cap A\neq \emptyset $
and
$N_{G_{h-1}}(v)\cap A\neq \emptyset $
. Without loss of generality, assume
$|N_{G_{h-1}}(u)\cap A|\geq 2$
. Let
$a\in N_{G_{h-1}}(v)\cap A$
and
$b\in N_{G_{h-1}}(u)\cap A \backslash \{a\}$
. Let
$G_{v,b}$
be the graph obtained by deleting the two vertices
$v,b$
from
$G_{h-1}$
. Notice that there are two disjoint paths
$P_1$
and
$P_2$
in
$G_{v,b}$
, where
$P_1$
is a path of order
$2s-1$
ending at a and
$P_2$
is a path of order
$k-2s-1$
ending at
$u\in C$
. We can extend
$P_1$
and
$P_2$
from a and
$u,y$
by adding
$av$
,
$ub$
such that the order of the new path is k, a contradiction.
So
$G_{h-1}\cong \Gamma $
. Hence,
$G\cong G_1\cong \cdots \cong G_{h-1}\cong \Gamma $
.
In the following, let
$H=H(\Gamma ;t)$
. Recall that
$t=\left \lfloor \frac {k}{2}\right \rfloor -1$
.
Claim 3 H is not empty.
Proof Suppose, to the contrary, that
$H=\emptyset $
. Choose a maximum clique in
$\Gamma $
, and denote it by X.
Let
$|X|=s$
. Recall that
$\Gamma [X]=K_s$
. Since
$H=\emptyset $
,
$s\leq t+1$
. Indeed, if
$s\geq t+2$
, then there is a
$K_{t+2}$
-clique in
$\Gamma $
. After all t-disintegrations of
$\Gamma $
, the
$K_{t+2}$
-clique is still a
$K_{t+2}$
-clique in H, contradicting the fact that
$H=\emptyset $
. This proves that
$s\leq t+1$
. By Lemma 11, we have
$\Gamma =S_{n, s-1}$
or after applying a series of EKO to
$\Gamma $
,
$\Gamma $
becomes a graph
$\Gamma ',$
which is a proper subgraph of
$S_{n, s-1}$
. Note that
$S_{n, t}$
is
$P_{k}$
-free because the longest path is of order at most
$2t+1$
and
$2t+1\leq k-1$
. Since
$S_{n, s-1}(s\leq t)$
and
$\Gamma '$
is a proper subgraph of
$S_{n, t}$
, we have
$\Gamma =S_{n, t}$
; otherwise, it contradicts the fact that
$\mathcal {P}(G)$
is maximum. If
$\Gamma =S_{n,t}$
and k is odd, then
$\Gamma $
is a proper subgraph of
$S^+_{n,t}$
, contradicting that
$\mathcal {P}(G)$
is maximum. If
$\Gamma =S_{n,t}$
and k is even, by Claim 2, we have
$G\cong \Gamma $
, contradicting the assumption that
$G\notin \mathcal {G}^2_{n,k}$
.
Claim 4 H is a clique.
Proof Suppose
$x,y \in V(H)$
are not adjacent in H. By Claim 1, there are an x-path and a y-path which are disjoint such that the sum of their orders is at least k. We choose such
$x,y\in V(H)$
that an x-path
$P_1$
and a y-path
$P_2$
satisfies that
$P_1$
and
$P_2$
are vertex-disjoint and
$|P_1|+|P_2|$
is maximum in H. We claim
$N_H(x) \subset V(P_1\cup P_2)$
and
$N_H(y) \subset V(P_1\cup P_2)$
. Suppose
$z \in N_H(x) $
and
$z \not \in V(P_1\cup P_2)$
. If
$\{y,z\} \in E(G)$
, then we get a path of order at least
$k+1$
, a contradiction. If y and z are nonadjacent, it is a contradiction to the choice of
$P_1$
. The same argument also holds for y. By Lemma 16, we get a path of order at least
$\min \{k,d_H(x)+d_H(y)+1 \}\geq \min \{k,2(t+1)+1\} \geq k$
, a contradiction. This proves Claim 4.
By a similar argument to the one for the cycle above, we can get the following claim.
Claim 5
H is a clique with the maximum size in
$\Gamma $
.
Claim 6 Let
$r-1=|V(H)|$
. Then,
$t+3\leq r \leq k-1$
. So,
$1\leq k-r\leq t$
.
Proof As
$H=H(\Gamma ;t)$
is a clique,
$r \geq t+3$
. We claim that
$r\leq k-1$
. Suppose that
$r\geq k$
. There is a path of order
$k-1$
in H. Furthermore, there is a
$P_k$
in
$\Gamma $
since
$\Gamma $
is connected, then there is a
$P_k$
in G, a contradiction. So,
$k-r\leq k-t-3=k-\left \lfloor \frac {k}{2}\right \rfloor -2\leq \left \lfloor \frac {k}{2}\right \rfloor -1=t$
. This proves Claim 6.
Claim 7 Let
$H'=H(\Gamma ;k-r)$
. Then,
$H \neq H'$
.
Proof Suppose
$H=H'$
. Notice that each vertex from
$V(G)\setminus V(H')$
has degree at most
$k-r$
in
$\Gamma $
in its time of deletion. So the size of the second largest maximal clique is at most
$k-r+1$
. By Lemma 10 and Claim 2,
$\Gamma $
is a proper subgraph of
$K_{k-r}\vee ((n-r+1)K_1\cup K_{2r-k-1})$
, then
$\mathcal {P}(\Gamma )< \mathcal {P}(K_{k-r}\vee ((n-r+1)K_1\cup K_{2r-k-1})),$
a contradiction. This proves the claim.
Next, we show that G contains a path of order at least k. By Claim 7,
$V(H) \subset V(H')$
and
$H \neq H'$
. We select
$x \in V(H) $
and
$y \in V(H') \setminus V(H)$
such that x and y are nonadjacent. By Claim 1, there are an x-path and a y-path which are disjoint such that the sum of their orders is at least k. We choose such
$x,y\in V(H)$
that an x-path
$P_1$
and a y-path
$P_2$
satisfies that
$P_1$
and
$P_2$
are vertex-disjoint and
$|P_1|+|P_2|$
is maximum in H. We claim
$N_H(x) \subset V(P_1\cup P_2)$
and
$N_{H'}(y) \subset V(P_1\cup P_2)$
by a similar discussion in Claim
$3$
. By Lemma 16, we get a path of order at least
$\min \{k, d_H(x)+d_{H'}(y)\} \geq \min \{k,r-2+k-r+2\}=k$
, a contradiction. This proves the theorem.
To prove Theorem 2.3, we need the following lemma.
Lemma 17 (Bondy–Chvátal [Reference Bondy and Chvátal4])
Let G be a graph on n vertices. For any two nonadjacent vertices
$u, v\in V(G)$
, if whenever
$\nu (G+uv)=k+1$
and
$d_G(u)+d_G(v)\geq 2k+1$
, then
$\nu (G)=k+1$
.
Though the following proof looks similar to the above one, we give the details as there are several differences that are important.
Proof of Theorem 2.3
The case
$n=2k+1$
is trivial, so we only consider the case
$n\geq 2k+2$
. We prove the theorem by contradiction. Let G be an n-vertex connected graph containing no
$M_{k+1}$
with the maximum
$\mathcal {P}(G)$
but
$G\notin \mathcal {G}^3_{n,k}$
. Since
$\mathcal {P}(G)$
is maximum, by Property (II), G is edge-maximal. Adding any new edge (i.e., joining any two non-adjacent vertices) will increase the value of
$\mathcal {P}(G)$
. Thus, G is edge-maximal. We have the following.
Claim 1 For any two non-adjacent vertices
$x,y\in V(G)$
,
$G+xy$
has a matching of size
$k+1$
, i.e.,
$\nu (G+xy)=k+1$
.
For any two adjacent vertices
$x,y\in V(G)$
, if neither
$N_G(x)\subset N_G(y)$
nor
$N_G(y)\subset N_G(x)$
, we use KO to get a new graph
$G_{xy}=G[x\rightarrow y]$
or
$G_{yx}=G[y\rightarrow x]$
. By Property (I), we have
$\mathcal {P}(G_{xy})\geq \mathcal {P}(G)$
and
$\mathcal {P}(G_{yx})\geq \mathcal {P}(G)$
. After a series of Kelmans Operations, the procedure will stop and result in a threshold graph, denoted by
$\Gamma $
. In the following, let
$G:=G_0, G_1, G_2,\dots , G_h:=\Gamma $
be a sequence of graphs, such that
$G_{i+1}=G_i[u_i\to v_i]$
, where
$u_iv_i\in E(G)$
and
$G_h$
is a threshold graph of G. Hence,
$\mathcal {P}(\Gamma )\geq \mathcal {P}(G)$
.
Claim 2 If
$\Gamma \in \mathcal {G}^3_{n,k}$
, then
$G\cong \Gamma $
.
Proof Suppose
$\Gamma =W_{n,2k+1,s}=K_{s}\vee ((n-2k+s-1)K_1\cup K_{2k-2s+1})$
, where
$1\leq s\leq k$
. We partition
$V(W_{n,2k+1,s})$
into three disjoint parts
$A,B,C$
, such that A consists of
$n-2k+s-1$
isolated vertices, B is a clique of order s, and C is a clique of order
$2k-2s+1$
; moreover,
$(A, B)$
is complete bipartite and
$B\cup C$
is a clique of order
$2k-s+1$
.
Now, we consider
$G_{h-1}$
. Recall that
$\Gamma =G_{h-1}[u_{h-1} \to v_{h-1}]$
. For simplicity, we denote
$u_{h-1}$
by u and
$v_{h-1}$
by v. By the definition of KO, we have
$N_\Gamma (u)\subset N_\Gamma (v)$
and
$uv\in E(\Gamma )$
. Notice that
$N_{\Gamma }(u)=N_{\Gamma }(v)$
when
$u,v\in B$
or
$u,v\in C$
. Thus,
$v\in B$
and
$u\in A\cup C$
. Suppose
$G_{h-1}\not \cong \Gamma $
. Then,
$N_{G_{h-1}}(u)\cap (A\cup C)\neq \emptyset $
,
$N_{G_{h-1}}(v)\cap (A\cup C)\neq \emptyset $
and
$A\cup C\subset N_{G_{h-1}}(u)\cup N_{G_{h-1}}(v)$
.
Suppose that
$v\in B$
and
$u\in A$
. We have
$B-v \subseteq N_{G_{h-1}}(u)\cap N_{G_{h-1}}(v)$
. Suppose
$N_{G_{h-1}}(v)\cap C=\emptyset $
or
$N_{G_{h-1}}(u)\cap A=\emptyset $
. Let
$a\in N_{G_{h-1}}(v)\cap A$
and
$b\in N_{G_{h-1}}(u)\cap C$
. Let
$G_{u,v,a,b}$
be the graph obtained by deleting the four vertices
$u,v,a,b$
from
$G_{h-1}$
. Since
$G_{u,v,a,b}\cong K_{s-1}\vee ((n-2k+s-3)K_1\cup K_{2k-2s})$
, there is an
$M_{k-1}$
in
$G_{u,v,a,b}$
as
$n-2k+s-3-(s-1)=n-2k-2\geq 0$
. We can extend
$M_{k-1}$
to
$M_{k+1}$
by adding
$bu$
and
$va$
, a contradiction. The case
$N_{G_{h-1}}(u)\cap C=\emptyset $
or
$N_{G_{h-1}}(v)\cap A=\emptyset $
is similar. Now consider the case
$N_{G_{h-1}}(x)\cap A\neq \emptyset $
and
$N_{G_{h-1}}(x)\cap C\neq \emptyset $
, where
$x\in \{u,v\}$
. Let
$a\in N_{G_{h-1}}(u)\cap A$
and
$b\in N_{G_{h-1}}(v)\cap C$
. Let
$G_{a,b,u,v}$
be the graph obtained by deleting
$a,b,u,v$
from
$G_{h-1}$
. Note that there is an
$M_{k-1}$
in
$G_{a,b,u,v}$
. We can extend
$M_{k-1}$
to
$M_{k+1}$
by adding
$au$
and
$bv$
, a contradiction.
Suppose that
$v\in B$
and
$u\in C$
. We have
$(B\cup C)-\{u,v\} \subseteq N_{G_{h-1}}(u)\cap N_{G_{h-1}}(v)$
. Since
$G_{h-1}\not \cong \Gamma $
,
$N_{G_{h-1}}(u)\cap A\neq \emptyset $
and
$N_{G_{h-1}}(v)\cap A\neq \emptyset $
. Without loss of generality, assume
$|N_{G_{h-1}}(u)\cap A|\geq 2$
. Let
$a\in N_{G_{h-1}}(v)\cap A$
and
$b\in N_{G_{h-1}}(u)\cap (A \backslash \{a\})$
. Let
$G_{b,u}$
be the graph obtained by deleting
$b,u$
from
$G_{h-1}$
. There is an
$M_k$
in
$G_{h-1}$
. We can extend
$M_k$
to
$M_{k+1}$
by adding
$bu$
, a contradiction.
So
$G_{h-1}\cong \Gamma $
. Hence,
$G\cong G_1\cong \cdots \cong G_{h-1}\cong \Gamma $
.
Let
$H=H(\Gamma ;k)$
.
Claim 3 H is not empty.
Proof Suppose to the contrary that
$H=\emptyset $
. Choose a maximum clique in
$\Gamma $
, and denote it by X.
Let
$|X|=s$
and
$|Y|=n-s$
. Recall that
$\Gamma [X]=K_s$
. Since
$H=\emptyset $
,
$s\leq k+1$
. Indeed, if
$s\geq k+2$
, then there is a
$K_{k+2}$
-clique in
$\Gamma $
. After all k-disintegrations of
$\Gamma $
, the
$K_{k+2}$
-clique is still a
$K_{k+2}$
-clique in H, contradicting the fact that
$H=\emptyset $
. This proves that
$s\leq k+1$
.
By Lemma 11, we have
$\Gamma =S_{n, s-1}$
or after applying a series of EKO to
$\Gamma $
,
$\Gamma $
becomes a graph
$\Gamma ',$
which is a proper subgraph of
$S_{n, s-1}$
. Note that
$S_{n, s-1}$
is
$M_{k+1}$
-free because the matching number is
$s-1\leq k$
. Since
$S_{n, s-1}(s\leq k+1)$
and
$\Gamma '$
is a proper subgraph of
$S_{n, k}$
, we have
$\Gamma =S_{n, k}$
; otherwise, it contradicts the fact that
$\mathcal {P}(G)$
is maximum. By Claim 2, we have
$G\cong S_{n,k}$
, which contradicts the assumption that
$G\notin \mathcal {G}^3_{n,k}$
. This proves the claim.
Claim 4 H is a clique.
Proof We shall show that H is a clique. Suppose
$x,y \in V(H)$
are not adjacent in H. Then, x and y are not adjacent in
$\Gamma $
. Since G is
$M_{k+1}$
-free,
$\Gamma $
is
$M_{k+1}$
-free. Since
$\mathcal {P}(G)$
is maximum and
$\mathcal {P}(\Gamma +xy)>\mathcal {P}(G)$
, we have
$\nu (\Gamma +xy)\geq k+1$
. Note that
$d_H(x)+d_H(y)\geq 2k+2$
. By Lemma 17,
$\nu (\Gamma )\geq k+1$
. As
$\nu (G)\geq \nu (\Gamma )\geq k+1$
, a contradiction which proves Claim 4.
Claim 5
H is a clique with the maximum size in
$\Gamma $
.
Proof Suppose that there exists another clique, say
$H'$
in
$\Gamma $
such that
$|H'|>|H|$
. Then, for any vertex
$v\in V(H')$
,
$d_{H'}(v)\geq |H'|-1\geq |H|\geq k+2$
. As
$H'$
is a clique in
$\Gamma $
, any vertex in
$H'$
cannot be deleted in
$H(\Gamma ;k)$
, and hence,
$H'\subseteq H$
, contradicting the fact that
$|H'|>|H|$
. This proves the claim.
Let
$r=|V(H)|$
.
Claim 6
$k+2\leq r\leq 2k$
, and so
$1\leq 2k+1-r\leq k-1.$
Proof As
$H=H(\Gamma ;k)$
is a clique,
$r \geq k+2$
. Suppose that
$r=2k+1$
, then there is an
$M_k$
in H. As
$n\geq 2k+2$
and
$\Gamma $
is connected, there is an
$M_{k+1}$
in
$\Gamma $
, and so G contains
$M_{k+1}$
as well, a contradiction. If
$r\geq 2k+2$
, there is an
$M_{k+1}$
in H, so G contains
$M_{k+1}$
as well. It is a contradiction. Now, we have
$k+2\leq r\leq 2k$
. This proves Claim 6.
Claim 7 Let
$H'=H(\Gamma ;2k+1-r)$
. Then,
$H \neq H'$
.
Proof Suppose
$H=H'$
. Notice that each vertex from
$V(G)\setminus V(H')$
has degree at most
$2k+1-r$
in
$\Gamma $
at the time of its deletion. So, the size of the second largest maximal clique is at most
$2k+2-r$
. By Lemma 10 and Claim 2,
$\Gamma $
is a proper subgraph of
$K_{2k-r+1}\vee ((n-r)K_1\cup K_{2r-2k-1})$
, then
$$ \begin{align*}\mathcal{P}(\Gamma)< \mathcal{P}(K_{2k-r+1}\vee ((n-r)K_1\cup K_{2r-2k-1})), \end{align*} $$
a contradiction. This proves the claim.
Finally, we claim that G contains an
$M_{k+1}$
. Note that
$V(H) \subset V(H')$
and
$H \neq H'$
. We select
$x \in V(H) $
and
$y \in V(H') \setminus V(H)$
such that x and y are nonadjacent. Note that Claim 1 is also true if we replace G with
$\Gamma $
. So by Claim 1, there is an
$M_{k+1}$
in
$\Gamma +xy$
. Observe that
$d_\Gamma (x)+d_\Gamma (y)\geq r-1+2k-r+2=2k+1$
, thus there is an
$M_{k+1}$
in
$\Gamma $
by Lemma 17, and so G contains
$M_{k+1}$
as well, a contradiction. This proves the theorem.
6 Concluding remarks
-
1. As remarked in [Reference Kopylov13], the classical Theorem 1.1 can imply Theorem 1.2. One may wonder whether we can deduce Theorem 2.2 from Theorem 2.1 or not. Indeed, we can consider the general problem: Let
$G_1,G_2$
be two graphs such that
$|V(G_1)|=|V(G_2)|$
and let
$\mathcal {C}(G_1)$
,
$\mathcal {C}(G_2)$
be feasible parameters. Suppose
$\mathcal {C}(G_1)>\mathcal {C}(G_2)$
. Is it always true that
$\mathcal {C}(G_1\vee K_1)>\mathcal {C}(G_2\vee K_1)$
? The answer is negative. In fact, it is false when we consider just a problem under the spectral radius condition. Consider the following example: let
$G_1=K_3\vee 5K_1$
and
$G_2=K_1\vee (K_5+2K_1)$
. Then,
$\lambda (G_1)=5<\lambda (G_2)=5.0695$
, but
$\lambda (G_1\vee K_1)=\lambda (K_4\vee 5K_1)=6.2170>\lambda (G_2\vee K_1)=\lambda (K_2\vee (K_5+2K_1))=6.1970$
. The following problem is still wide open.Problem 3 Let
$G_1,G_2$
be two graphs with the same vertex set and
$\lambda (G_1)\geq \lambda (G_2)$
. Determine which graphs
$G_1,G_2$
satisfying the property that
$\lambda (G_1\vee K_1)\geq \lambda (G_2\vee K_1)$
. -
2. Theorem 2.1 tells us how a feasible graph parameter behaves under constraints on the circumference of
$2$
-connected graphs. It is natural to ask how the parameter behaves in connected graphs or general graphs. -
3. When
$\mathcal {P}$
is weakly feasible, we can determine the extremal values of
$\mathcal {P}$
but not the extremal graphs. Can the corresponding extremal graphs also be determined with more careful arguments?
Acknowledgements
The authors would like to thank Yair Caro for his helpful suggestions. They also want to express their sincere gratitude to the anonymous referee for carefully reading the manuscript and providing many helpful comments.
