# Sufficient Conditions for Graphs to Bek-Connected, Maximally Connected, and Super-Connected

Authors: Zhen-Mu Hong; Zheng-Jiang Xia; Fuyuan Chen; Lutz Volkmann
Journal: Complexity
 (2021)

---

## Abstract

LetG be a connected graph with minimum degree δG and vertex-connectivity κG. The graph G is k-connected if κG≥k, maximally connected if κG=δG, and super-connected if every minimum vertex-cut isolates a vertex of minimum degree. In this paper, we present sufficient conditions for a graph with given minimum degree to be k-connected, maximally connected, or super-connected in terms of the number of edges, the spectral radius of the graph, and its complement, respectively. Analogous results for triangle-free graphs with given minimum degree to be k-connected, maximally connected, or super-connected are also presented.


---

## Body

## 1. Introduction

LetG=V,E be a simple connected undirected graph, where V=VG is the vertex-set of G and E=EG is the edge-set of G. The order and size of G are defined by n=VG and m=EG, respectively; dGx is the degree of a vertex x in G, that is, the number of edges incident with x in G; δG=mindGx:x∈VG is the minimum degree of G. For a subset X⊂VG, use GX to denote the subgraph of G induced by X. For two subsets X and Y of VG, let X,Y be the set of edges between X and Y. The complement of G is denoted by G¯. Let G1∪G2 denote the disjoint union of graphs G1 and G2, and let G1∨G2 denote the graph obtained from G1∪G2 by joining each vertex of G1 to each vertex of G2. The graph G is called a triangle-free graph if G contains no triangle. Denote by ρG the largest eigenvalue or the spectral radius of the adjacency matrix of G and it is called the spectral radius of G. If G is connected, then, by Perron-Frobenius Theorem, ρG is simple and there exists a unique (up to a multiple) corresponding positive eigenvector.Avertex-cut of a connected graph G is a set of vertices whose removal disconnects G. The vertex-connectivity or simply the connectivityκ=κG of a connected graph G is the minimum cardinality of a vertex-cut of G if G is not complete, and κG=n−1 if G is the complete graph Kn of order n. A vertex-cut S is a minimum vertex-cut or a κ-cut of G if S=κG. Apparently, κG≤δG for any graph G. The graph G is k-connected if κG≥k, maximally connected if κG=δG, and super-connected (or super-κ) if every minimum vertex-cut isolates a vertex of minimum degree. Hence, every super-connected graph is also maximally connected. An edge-cut of a connected graph G is a set of edges whose removal disconnects G. The edge connectivityλ=λG of a connected graph G is defined as the minimum cardinality of an edge-cut over all edge-cuts of G. An edge-cut S is a minimum edge-cut if S=λG. The inequality λG≤δG is obvious. The graph G is maximally edge-connected if λG=δG, and it is super-edge-connected if every minimum edge-cut consists of edges incident with a vertex of minimum degree. Therefore, every super-edge-connected graph is also maximally edge-connected. For graph-theoretical terminology and notation not defined here, one can refer to [1, 2].Sufficient conditions for graphs to be maximally (edge-) connected or super-(edge-) connected were given by several authors, depending on the order, the maximum and minimum degree, the diameter, the girth, the degree sequence, the clique number and so on. The paper in [3] by Hellwig and Volkmann gives a survey on this topic. Recently, Volkmann and Hong [4] proved that a connected graph or a connected triangle-free graph is maximally edge-connected or super-edge-connected if the number of edges is large enough, and the results corresponding to triangle-free graphs were generalized to connected graphs with given clique number by Volkmann [5].On the other hand, the relationship between graph properties and eigenvalues has attracted much attention. Fiedler [6] initiated the research on the relationship between graph connectivity and graph eigenvalues, and Fiedler and Nikiforov [7] initiated the investigation on the spectral conditions for graphs to be Hamiltonian or traceable. Cioabă [8] investigated the relationship between edge-connectivity and adjacency eigenvalues of regular graphs. From then on, the edge-connectivity problem has been intensively studied by many researchers, such as Duan et al. [9], Gu et al. [10], Liu et al. [11], Liu et al. [12], and Suil O [13]. For vertex-connectivity, Li [14] presented sufficient conditions for a graph to be k-connected using spectral radius and signless Laplacian spectral radius; Feng et al. [15] demonstrated sufficient conditions based on spectral radius for a graph to be k-connected and k-edge-connected; Feng et al. [16] obtained a tight sufficient condition for a connected graph with fixed minimum degree to be k-connected based on its spectral radius, for sufficiently large order. Vertex-connectivity and the second largest adjacency eigenvalue of regular graphs were studied by Abiad et al. [17], Cioabă and Gu [18], O [19], and Zhang [20]. The relationship between vertex-connectivity and adjacency eigenvalues or Laplacian eigenvalues of graphs has been investigated by Hong et al. [21–23] and Liu et al. [24].Motivated by the researches mentioned above, this paper presents sufficient conditions for a graph with given minimum degree to bek-connected, maximally connected, or super-connected in terms of the number of edges, the spectral radius of the graph, or its complement, respectively. In addition, we also give sufficient conditions for a triangle-free graph with given minimum degree to be k-connected, maximally connected, or super-connected in terms of the number of edges or its spectral radius, respectively. The results on k-connected graph in this paper improve the result in [16] by Feng et al. to some extent.The rest of this paper is organized as follows. In Section2, we present sufficient conditions for a graph with given minimum degree to be k-connected in terms of the number of edges, the spectral radius of the graph, and its complement, respectively. In terms of the same parameters as in Section 2, by setting k=δ, we get sufficient conditions for a graph with given minimum degree to be maximally connected in Section 3, and we obtain sufficient conditions for a graph with given minimum degree to be super-connected in Section 4. In Section 5, sufficient conditions for a triangle-free graph to be k-connected, maximally connected, or super-connected are acquired in terms of the number of edges and the spectral radius of the graph, respectively.


## 2.k-Connected Graphs

LetG be a connected graph of order n, minimum degree δ, and vertex-connectivity κ. If n≤4 or δ=1, then κ=δ. If δ=n−1, then G=Kn and κ=δ. If δ=n−2, then when u and v are nonadjacent, the other n−2 vertices are all common neighbors of u and v. It is necessary to delete all common neighbors of some pair of vertices to separate the graph, so κ≥n−2=δ. Therefore, we only need to consider n≥5 and 2≤δ≤n−3 in the following.Theorem 1.
LetG be a connected graph of order n≥5, size m, and minimum degree δ≥k≥2.(a)
If(1)m≥12nn−1−δ−k+2n−δ−1,thenG is k-connected, unless G=Kk−1∨Kδ−k+2∪Kn−δ−1.(b)
Ifn≥1/2k+1δ−k+2+δ+2 and(2)m≥12nn−1−12δ−k+22n−2δ+k−3,thenGisk-connected, unlessGis a subgraph ofKk−1∨Kδ−k+2∪Kn−δ−1.Proof.
Letκ=κG. On the contrary, suppose that G is not k-connected; that is, 1≤κ≤k−1. Let S be an arbitrary minimum vertex-cut, and let X0,X1,…,Xp−1 (p≥2), denote the vertex sets of the components of G−S, where X0≤X1≤⋯≤Xp−1. Each vertex in X0 is adjacent to at most X0−1 vertices of X0 and κ=S vertices of S. Thus,(3)δX0≤∑x∈X0dx≤X0X0+κ−1,and so X0≥δ−κ+1. Let Y=∪i=1p−1Xi; then Y=n−κ−X0. Therefore,(4)δ−κ+1≤X0≤Y≤n−δ−1.
SinceG−S is disconnected, there are no edges between X0 and Y in G and(5)m≤12nn−1−X0⋅Y.(a)
Since we suppose thatG is not k-connected, it suffices to prove G=Kk−1∨Kδ−k+2∪Kn−δ−1. By (4) and X0+Y=n−κ, and since κ≤k−1, we obtain(6)X0⋅Y≥δ−κ+1n−δ−1≥δ−k+2n−δ−1.Substituting (6) into (5), it follows that(7)m≤12nn−1−δ−k+2n−δ−1.Combining this with (1), we obtain m=1/2nn−1−δ−k+2n−δ−1. Hence, all the inequalities in (6) must be equalities and so κ=k−1, X0=δ−k+2, and Y=n−δ−1. Thus, G is obtained from Kn by deleting all the edges of the complete bipartite subgraph KX0,Y of Kn. That is, GX0=Kδ−k+2, GS=Kk−1, GY=Kn−δ−1, and G=Kk−1∨Kδ−k+2∪Kn−δ−1.(b)
To prove thatG is a subgraph of Kk−1∨Kδ−k+2∪Kn−δ−1, we first show that X0=δ−k+2. Suppose that X0≥δ−k+3. Since X0≤Y, X0+Y=n−κ, and κ≤k−1, we have(8)X0⋅Y≥δ−k+3n−κ−δ−k+3≥δ−k+3n−δ−2.
Substituting (8) into (5), it follows that(9)m≤12nn−1−δ−k+3n−δ−2.
Combining this with (2), it is easy to get n≤1/2k+1δ−k+2+δ+2. By the hypothesis, we have n=1/2k+1δ−k+2+δ+2. Hence, m=1/2nn−1−δ−k+3n−δ−2 and all the inequalities in (8) must be equalities. Thus, κ=k−1, X0=δ−k+3, Y=n−δ−2, and G is obtained from Kn by deleting all the edges of the complete bipartite subgraph KX0,Y of Kn. That is, G=Kk−1∨Kδ−k+3∪Kn−δ−2. However, δG=δKk−1∨Kδ−k+3∪Kn−δ−2=δ+1>δ, a contradiction. Thus, X0≤δ−k+2. Combining this with X0≥δ−κ+1≥δ−k+2, we get X0=δ−k+2. Since S=κ≤k−1 and dGx≥δ for each x∈X0, we have that each vertex of X0 is adjacent to each vertex of S and S=k−1. Therefore, GX0∪S=Kδ+1 and G is a subgraph of Kk−1∨Kδ−k+2∪Kn−δ−1.Theorem 2.
LetG be a connected graph of order n and minimum degree δ≥k≥2. If(10)ρG≥ρKk−1∨Kδ−k+2∪Kn−δ−1,thenGisk-connected, unlessG=Kk−1∨Kδ−k+2∪Kn−δ−1, whereρKk−1∨Kδ−k+2∪Kn−δ−1is the largest root of the equation(11)λ3−n−3λ2+δ−k+2n−δ−1−2n+3λ+δ−k+2n−δ−1k−n+1=0.Proof.
Letκ=κG. Assume that (10) holds but 1≤κ≤k−1. Let S be an arbitrary minimum vertex-cut of G, and let X0,X1,…,Xp−1 (p≥2), denote the vertex-sets of the components of G−S, where X0≤X1≤⋯≤Xp−1. Each vertex in Xi is adjacent to at most Xi−1 vertices of Xi and κ=S vertices of S. Thus,(12)δXi≤∑x∈Xidx≤XiXi−1+κ,and so Xi≥δ−κ+1 for each i=0,1,…,p−1. Let Y=∪i=1p−1Xi. Then, δ−κ+1≤X0≤Y≤n−δ−1 and X0+Y=n−κ. Since there are no edges between X0 and Y in G, G is a subgraph of Kκ∨KX0∪KY and ρG≤ρKκ∨KX0∪KY.
Next, we will show(13)ρKκ∨KX0∪KY≤ρKκ∨Kδ−κ+1∪Kn−δ−1≤ρKk−1∨Kδ−k+2∪Kn−δ−1.
DenoteGa,b,κ=Kκ∨Ka∪Kb for short, where b≥a≥δ−κ+1 and a+b+κ=n. Let x=x1,x2,…,xnT be the unique positive unit eigenvector corresponding to ρGa,b,κ. By symmetry, let x≔xi for any i∈Ka; y≔xj for any j∈Kκ; z≔xℓ for any ℓ∈Kb. According to λxi=∑ij∈EGa,b,κxj and the uniqueness of x, we have that ρGa,b,κ is the largest root of the following equations:(14)λx=a−1x+κy,λy=ax+κ−1y+bz,λz=κy+b−1z.
Thus,ρGa,b,κ is the largest root of the equation(15)fλ;a,b,κ≔λ3−n−3λ2+ab−2n+3λ+abκ+1−n+1=0.
Then, we have(16)fλ;a,b,κ−fλ;δ−κ+1,n−δ−1,κ=λ+κ+1ab−δ−κ+1n−δ−1≥0,for any λ>0 and b≥a≥δ−κ+1. Therefore, ρGa,b,κ≤ρGδ−κ+1,n−δ−1,κ for any b≥a≥δ−κ+1, which means that(17)ρKκ∨KX0∪KY≤ρKκ∨Kδ−κ+1∪Kn−δ−1.
SinceKκ∨Kδ−κ+1∪Kn−δ−1 is a subgraph of Kk−1∨Kδ−k+2∪Kn−δ−1 for any κ≤k−1,(18)ρKκ∨Kδ−κ+1∪Kn−δ−1≤ρKk−1∨Kδ−k+2∪Kn−δ−1.
Hence, from the discussion above, we have(19)ρG≤ρKκ∨KX0∪KY≤ρKκ∨Kδ−κ+1∪Kn−δ−1≤ρKk−1∨Kδ−k+2∪Kn−δ−1.
By (10), the above inequalities must be equalities. Thus, X0=δ−k+2, κ=k−1, Y=n−δ−1, and so G=Kk−1∨Kδ−k+2∪Kn−δ−1. The result follows from (15).Remark 1.
In Corollary 3.5 in [16], the authors showed that if G is a connected graph of minimum degree δG≥δ≥k≥3 and order n≥δ−k+2k2−2k+4+3, and ρG≥ρKk−1∨Kδ−k+2∪Kn−δ−1, then G is k-connected, unless G=ρKk−1∨Kδ−k+2∪Kn−δ−1. Apparently, without restriction on the order of graph, Theorem 2 improves Corollary 3.5 in [16].Theorem 3.
LetG be a connected graph of order n and minimum degree δ≥k≥3. If G is a subgraph of Kk−1∨Kδ−k+2∪Kn−δ−1 and n≥1/2δ−k+2k2−2k+7, then(20)ρG<n−δ+k−3,unlessG=Kk−1∨Kδ−k+2∪Kn−δ−1.Proof.
DenoteH=Kk−1∨Kδ−k+2∪Kn−δ−1 for short. Let x=x1,x2,…,xnT be the unique positive unit eigenvector corresponding to ρG. Recall that Rayleigh’s principle implies that(21)ρG=xTAGx=2∑ij∈EGxixj.
Assume thatG is a proper subgraph of H. Clearly, we could assume that G is obtained by omitting just one edge uv of H. Let X,Y,Z be the set of vertices of H of degree δ,n−1,n−δ+k−3, respectively, where X=δ−k+2, Y=k−1, and Z=n−δ−1. Since δG=δ, G must contain all the edges between X and Y. Therefore, u,v⊂Y∪Z, with three possible cases: (a) u,v⊂Y ; (b) u∈Y,v∈Z; and (c) u,v⊂Z. We shall show that case (c) yields a graph whose spectral radius is not smaller than the spectral radius of the graph in case (b) and that case (b) yields a graph whose spectral radius is not smaller than the spectral radius of the graph in case (a).
Firstly, suppose that case (a) occurs; that is,u,v⊂Y. Choose a vertex w∈Z. If xu≥xw, then by removing the edge vw and adding the edge uv we obtain a new graph G1 which is covered by case (b). By the Rayleigh principle,(22)ρG1−ρG≥xTAG1x−xTAGx=2xvxu−xw≥0.
Ifxw>xu, then by removing all the edges between X and u and adding all the edges between X and w we obtain a new graph G1′ which is also covered by case (b). By the Rayleigh principle,(23)ρG1′−ρG≥xTAG1′x−xTAGx=2xw−xu∑i∈Xxi>0.
Secondly, suppose that case (b) occurs; that is,u∈Y,v∈Z. Choose a vertex w∈Z and w≠v. If xu≥xw, then by removing the edge vw and adding the edge uv we obtain a new graph G2 which is covered by case (c). By the Rayleigh principle,(24)ρG2−ρG≥xTAG2x−xTAGx=2xvxu−xw≥0.
Ifxw>xu, then by removing all the edges between X and u and adding all the edges between X and w we obtain a new graph G2′ which is also covered by case (c). By the Rayleigh principle,(25)ρG2′−ρG≥xTAG2′x−xTAGx=2xw−xu∑i∈Xxi>0.
Therefore, we could assume thatu,v∈Z. By symmetry, let x≔xi for any i∈X; y≔xj for any j∈Y; z≔xℓ for any ℓ∈Z,u,v; and t≔xu=xv. According to λxi=∑ij∈EGxj and the uniqueness of x, we have that ρ is the largest root of following equations:(26)λx=δ−k+1x+k−1y,λy=δ−k+2x+k−2y+n−δ−3z+2t,λz=k−1y+n−δ−4z+2t,λt=k−1y+n−δ−3z.
Thus,ρG is the largest root of the equation(27)fλ≔λ4−n−5λ3+n−δ−1δ−k−2−4δ+7λ2+δk+2δ+2n−δ+k−3−k2+3n−1+6λ+2δ−k+1kn−δ−2−1+k−1n−δ−3=0.
By some basic calculations, we have(28)fn−δ+k−3=2n2−δ−k+2k2−2k+7n+δ−k+2δ−k+1k2−2k+5−2k−3.
Setgx=2x2−δ−k+2k2−2k+7x+δ−k+2δ−k+1k2−2k+5−2k−3. It is easy to see that the function gx is strictly increasing when x>1/2δ−k+2k2−2k+7. Since n≥1/2δ−k+2k2−2k+7>1/4δ−k+2k2−2k+7, we get(29)fn−δ+k−3=gn≥g12δ−k+2k2−2k+7=δ−k+2δ−k+1k2−2k+5−2k−3≥δ−k+2k2−4k+11>0.
By3≤k≤δ≤n−3 and n≥1/2δ−k+2k2−2k+7, we have n≥2δ−k+3 and then(30)fn−δ+k−4=−n3+4δ−k+3n2−k2−8k+5δ+23δ−k+2−5n+k2−5k+2δ+15δ−k+2−2δ−5δ−k+2+2=−nn−2δ−k+32−k2−4k+δ+7δ−k+2+1n−2δ−k+3−δ−k+2k2−3k+3δ−k+3+kk−1≤−23⋅3+kk−1<0,f0=2δ−k+1kn−δ−2−1+k−1n−δ−3≥2k−1>0, f−2=−2k−2δ−k+2+2<0, and f−∞>0. Therefore, it is easy to find that the largest root of fx=0 is in the interval n−δ+k−4,n−δ+k−3, which yields ρG<n−δ+k−3.The following lemma gives a sharp upper bound of the spectral radius of connected graphs with given number of edges and minimum degree.Lemma 1 (see [25]).
LetG be a connected graph with n vertices and m edges. Let δ=δG be the minimum degree of G and let ρG be the spectral radius of the adjacency matrix of G. Then,(31)ρG≤δ−12+2m−δn+δ+124.Equality holds if and only ifG is either a regular graph or a bidegreed graph in which each vertex is of degree either δ or n−1.Theorem 4.
LetG be a connected graph of order n and minimum degree δ≥k≥3. If n≥1/2δ−k+2k2−2k+7 and(32)ρG≥n−δ+k−3,then G is k-connected, unless G=Kk−1∨Kδ−k+2∪Kn−δ−1.Proof.
On the contrary, suppose thatκG<k. Since G is connected and ρG≥n−δ+k−3, by Lemma 1, we have(33)n−δ+k−3≤ρG≤δ−12+2EG−δn+δ+124,which yields(34)EG≥12nn−1−12δ−k+22n−2δ+k−3.
Sincen≥1/2δ−k+2k2−2k+7, we obtain n≥1/2k+1δ−k+2+δ+2. By Theorem 1 (b), G is a subgraph of Kk−1∨Kδ−k+2∪Kn−δ−1. Since ρG≥n−δ+k−3, by Theorem 3, G=Kk−1∨Kδ−k+2∪Kn−δ−1. The proof is completed.Remark 2.
In Theorem 3.4 in [16], the authors proved that if G is a connected graph of minimum degree δG≥δ≥k≥3 and order n≥δ−k+2k2−2k+4+3, and ρG≥n−δ+k−3, then G is k-connected unless G=ρKk−1∨Kδ−k+2∪Kn−δ−1. Obviously, Theorem 4 improves Theorem 3.4 in [16] from the perspective of the restriction on the order of graph.Another sufficient condition for graphs to bek-connected can be obtained by using the spectral radius of the complement of a graph.Theorem 5.
LetG be a connected graph of order n≥5 and minimum degree δ≥k≥2. If(35)ρG¯≤δ−k+2n−δ−1,thenGisk-connected, unlessG=Kk−1∨Kδ−k+2∪Kn−δ−1.Proof.
Letκ=κG. Assume that (35) holds but 1≤κ≤k−1. Let S be an arbitrary minimum vertex-cut of G, and let X0,X1,…,Xp−1 (p≥2), denote the vertex-sets of the components of G−S, where X0≤X1≤⋯≤Xp−1. Each vertex in Xi is adjacent to at most Xi−1 vertices of Xi and κ=S vertices of S. Thus,(36)δXi≤∑x∈Xidx≤XiXi−1+κ,and so Xi≥δ−κ+1 for each i=0,1,…,p−1. Let Y=∪i=1p−1Xi. Then, δ−κ+1≤X0≤Y≤n−δ−1 and X0+Y=n−κ. Since there are no edges between X0 and Y in G, KX0,Y is a subgraph of G¯. Thus,(37)ρG¯≥ρKX0,Y=X0⋅Y=X0n−κ−X0≥δ−κ+1n−δ−1≥δ−k+2n−δ−1.
By (35), the above inequalities must be equalities. Thus, X0=δ−k+2, κ=k−1 and G¯=Kδ−k+2,n−δ−1, and so G=Kk−1∨Kδ−k+2∪Kn−δ−1.


## 3. Maximally Connected Graphs

IfκG=δG, then G is maximally connected. Therefore, by setting k=δ in Theorem 1, we obtain the following theorem.Theorem 6.
LetG be a connected graph of order n≥5, size m, and minimum degree δ≥2.(a)
Ifm≥n−22+2δ−1, thenGis maximally connected, unlessG=Kδ−1∨K2∪Kn−δ−1.(b)
Ifn≥2δ+3andm≥n−22+δ, thenGis maximally connected, unlessGis a subgraph ofKδ−1∨K2∪Kn−δ−1.Theorem 7.
LetG be a connected graph of order n≥5 and minimum degree δ≥2. If(38)ρG≥δ−12+n−δ−1n−4+δ+124,thenGis maximally connected, unlessG=Kn−4∨K2∪K2.Proof.
On the contrary, suppose thatκG<δ. Since G is connected, by (38) and Lemma 1, we have(39)δ−12+n−δ−1n−4+δ+124≤ρG≤δ−12+2EG−δn+δ+124,which yields(40)EG≥n−22+2δ−1.
By Theorem6 (a), G=Kδ−1∨K2∪Kn−δ−1. To complete the proof, we only need to show δ=n−3.
SinceEG=n−22+2δ−1, the equalities hold in (39). Thus, by Lemma 1, G is either a regular graph or a bidegreed graph in which each vertex is of degree δ or n−1. However, the vertices of G have degrees from the set δ,n−3,n−1. Therefore, δ=n−3 and the result follows.By settingk=δ in Theorem 2, we obtain the following result.Theorem 8.
LetG be a connected graph of order n≥5 and minimum degree δ≥2. If(41)ρG≥ρKδ−1∨K2∪Kn−δ−1,thenGis maximally connected, unlessG=Kδ−1∨K2∪Kn−δ−1, whereρKδ−1∨K2∪Kn−δ−1is the largest root of the equation(42)λ3−n−3λ2−2δ−1λ+2δn−δ−1−n+1=0.Theorem 9.
LetG be a connected graph of order n and minimum degree δ≥2. If n≥δ2−2δ+7 and(43)ρG≥n−3,then G is maximally connected, unless G=Kδ−1∨K2∪Kn−δ−1.Proof.
Setk=δ in the proofs of Theorems 3 and 4. If δ≥3, then the result follows from Theorem 4. If δ=2, then case (a) cannot occur in the proof of Theorems 3. In Theorem 3, by noting that fn−3>0, fn−4<0, f0>0, f−3=23−4<0, and f−∞>0, we have ρG<n−3 and so Theorem 3 holds for δ=k=2. Hence, Theorem 4 also holds for δ=k=2 and the result follows.Remark 3.
In the proof of Theorem3, if we take k=δ≥2 and n=δ2−2δ+6, then fn−3=gn=gδ2−2δ+6=10−4δ<0 when δ≥3. Notice that f+∞=+∞. So, the largest root of fx=0 is greater than n−3 if δ≥3, and it follows that ρG>n−3. That is to say, the requirement n≥δ2−2δ+7 in Theorem 9 is best possible when δ≥3.By settingk=δ in Theorem 5, we have the following result.Theorem 10.
LetG be a connected graph of order n≥5 and minimum degree δ≥2. If(44)ρG¯≤2n−δ−1,then G is maximally connected, unless G=Kδ−1∨K2∪Kn−δ−1.


## 4. Super-Connected Graphs

For any connected graphG of order n, if 2≤n≤4, then G is super-κ. Therefore, n≥5 is considered in this section.Theorem 11.
LetG be a connected graph of order n≥5, size m, and minimum degree δ. If(45)m≥n−22+2δ,thenGis super-κ, unlessG=Kδ∨K2∪Kn−δ−2−e, wheree=xyis an edge ofKδ∨K2∪Kn−δ−2withdx=δ+1anddy=n−1.Proof.
Sincem≥n−22+2δ, by Theorem 6 (a), κG=δ. On the contrary, suppose that G is not super-κ. Let S be an arbitrary minimum vertex-cut with δ vertices, and let X0,X1,…,Xp−1 (p≥2) denote the vertex-sets of the components of G−S, where 2≤X0≤X1≤⋯≤Xp−1. Denote Y=∪i=1p−1Xi. Since G−S is disconnected, there are no edges between X0 and Y in G, and(46)m≤12nn−1−X0⋅Y.
Thus, byX0+Y=n−δ and 2≤X0≤Y≤n−δ−2, we have(47)m≤12nn−1−X0⋅Y≤12nn−1−2n−δ−2=n−22+2δ+1.
Ifm=n−22+2δ+1, then all the inequalities in the above proof must be equalities. It is deduced that p=2, X0=2, Y=n−δ−2, and dGs=n−1 for each s∈S, dGX0x=1 for each x∈X0, and dGYy=n−δ−3 for each y∈Y. That is, GX0=K2, GS=Kδ, GY=Kn−δ−2, and G≅Kδ∨K2∪Kn−δ−2. However, δG=δ+1>δ, which is a contradiction. Therefore, m≤n−22+2δ. By (45), m=n−22+2δ.
Next, we show thatG is a proper subgraph of Kδ∨K2∪Kn−δ−2. It suffices to prove that X0=2 and p=2.
IfX0≥3, then n≥δ+6. Combining (45) with (46), we obtain(48)n−22+2δ≤m≤12n2−n−X0⋅Y≤12n2−n−3n−δ−3≤n−22+2δ.
All the above inequalities must be equalities, and soX0=Y=3, n=δ+6, and G≅Kδ∨K3∪K3. However, δG=δ+2>δ, which is a contradiction. Therefore, X0=2.
Ifp≥3, then n≥δ+6. Let Y1=∪i=2p−1Xi. Then X1+Y1=n−δ−2 and 2=X0≤X1≤Y1≤n−δ−4. Since G−S is disconnected, there are no edges among X0, X1, and Y1 in G (i.e., X0,X1=∅, X0,Y1=∅, X1,Y1=∅), and(49)m≤12n2−n−X0⋅X1+Y1−X1Y1≤12n2−n−2n−δ−2−2⋅2=n−22+2δ−3<n−22+2δ,which is a contradiction. Therefore, p=2.
LetH=Kδ∨K2∪Kn−δ−2. Then G⊂H and EG=EH−1. Therefore, G=H−e. Since δH=δ+1 and δG=δ, e=xy is an edge of H with dx=δ+1 and dy=n−1.Theorem 12.
LetG be a connected graph of order n≥5 and minimum degree δ. If(50)ρG≥δ−12+2+n−δ−1n−4+δ+124,then G is super-κ.Proof.
On the contrary, suppose thatG is not super-κ. Since G is connected, by (50) and Lemma 1, we have(51)2+n−δ−1n−4+δ+124≤ρG−δ−12≤2EG−δn+δ+124,which yields(52)EG≥n−22+2δ.
By Theorem11, G=Kδ∨K2∪Kn−δ−2−e, where e=xy is an edge of Kδ∨K2∪Kn−δ−2 with dx=δ+1 and dy=n−1.
SinceEG=n−22+2δ, the equalities hold in (51). Thus, by Lemma 1, G is either a regular graph or a bidegreed graph in which each vertex is of degree δ or n−1. However, the vertices of G have degree from the set δ,δ+1,n−3,n−2,n−1. Thus, G cannot be a bidegreed graph, which yields a contradiction. Hence, G is super-κ.Theorem 13.
LetG be a connected graph of order n≥5 and minimum degree δ. If(53)ρG≥ρKδ∨K2∪Kn−δ−2,thenGis super-κ, whereρKδ∨K2∪Kn−δ−2is the largest root of the equation(54)λ3−n−3λ2−2δ+1λ+2δ+1n−δ−2−n+1=0.Proof.
On the contrary, suppose thatG is not super-κ. Let S be an arbitrary minimum vertex-cut with κ≤δ vertices, and let X0,X1,…,Xp−1 (p≥2) denote the vertex-sets of the components of G−S, where 2≤X0≤X1≤⋯≤Xp−1. Denote Y=∪i=1p−1Xi. Then 2≤X0≤Y≤n−κ−2 and X0+Y=n−κ. Since there are no edges between X0 and Y in G, G is a subgraph of Kκ∨KX0∪KY and ρG≤ρKκ∨KX0∪KY.
According to (15) in the proof of Theorem 2, ρKκ∨KX0∪KY is the largest root of the equation(55)fλ;X0,Y,κ≔λ3−n−3λ2+X0Y−2n+3λ+X0Yκ+1−n+1=0.
Then, we have(56)fλ;X0,Y,κ−fλ;2,n−κ−2,κ=λ+κ+1X0Y−2n−κ−2≥0,for any λ>0 and Y≥X0≥2. Therefore, ρKκ∨KX0∪KY≤ρKκ∨K2∪Kn−κ−2.
SinceKκ∨K2∪Kn−κ−2 is a subgraph of Kδ∨K2∪Kn−δ−2 for any κ≤δ, we get(57)ρKκ∨K2∪Kn−κ−2≤ρKδ∨K2∪Kn−δ−2.
Hence, from the above discussion, we obtain(58)ρG≤ρKκ∨KX0∪KY≤ρKκ∨K2∪Kn−κ−2≤ρKδ∨K2∪Kn−δ−2.
By (53), the above inequalities must be equalities. Thus, X0=2, κ=δ, Y=n−δ−2, and G=Kδ∨K2∪Kn−δ−2. However, δG=δ+1>δ, which is a contradiction. The result follows.Theorem 14.
LetG be a connected graph of order n≥5 and minimum degree δ. If(59)ρG¯≤2n−δ−2,thenGis super-κ.Proof.
Assume that (59) holds but G is not super-κ. Let S be an arbitrary minimum vertex-cut of G with κ≤δ vertices, and let X0,X1,…,Xp−1 (p≥2), denote the vertex-sets of the components of G−S, where 2≤X0≤X1≤⋯≤Xp−1. Denote Y=∪i=1p−1Xi. Then 2≤X0≤Y≤n−κ−2 and X0+Y=n−κ. Since there are no edges between X0 and Y in G, KX0,Y is a subgraph of G¯. Thus,(60)ρG¯≥ρKX0,Y=X0⋅Y=X0n−κ−X0≥2n−κ−2≥2n−δ−2.
By (59), the above inequalities must be equalities. Thus, X0=2, κ=δ, and G¯=K2,n−δ−2, and so G=Kδ∨K2∪Kn−δ−2. However, δG=δKδ∨K2∪Kn−δ−2=δ+1>δ, a contradiction. This completes the proof.


## 5. Sufficient Conditions for Triangle-Free Graphs

Let us extend an interesting result by applying the famous theorem of Mantel [26] and Turán [27].Theorem 15 (see [26, 27]).
For any triangle-free graphG of order n, we have EG≤⌊1/4n2⌋, with equality if and only if G=K⌊n/2⌋,⌈n/2⌉.Theorem 16.
LetG be a connected triangle-free graph of order n, size m, and minimum degree δ≥k≥2. If(61)m≥δ2+14n−2δ+k−12,then G is k-connected, unless VG=X∪S∪Y and S is a minimum vertex-cut of G with GS=Kk−1¯, GX∪S=Kδ,δ, and GY∪S=K⌊n−2δ+k−1/2⌋,⌈n−2δ+k−1/2⌉.Proof.
Letκ=κG. On the contrary, suppose that κ≤k−1. Let S be a minimum vertex-cut of G, and let X,Y1,…,Yp−1 (p≥2) denote the vertex-sets of the components of G−S, where X≤Y1≤⋯≤Yp−1. Set Y=∪i=1p−1Yi. Then X≤Y and X+Y=n−κ. By Theorem 15, we deduce that(62)EGX∪S≤X+S24,EGY∪S≤Y+S24,with equalities if and only if(63)GX∪S=KX+S/2,X+S/2,GY∪S=KY+S/2,Y+S/2.
Ifx∈X, then δ≤dGx≤X+S. The assumption κ≤k−1≤δ−1 implies that x has at least one neighbor y∈X. Since G is triangle-free, we deduce that NGx∩NGy=∅, where NGx is the neighbor set of x. As NGx∪NGy⊆X∪S, it follows that(64)X+S=X∪S≥NGx∪NGy=NGx+NGy≥2δ,and thus X≥2δ−S=2δ−κ. Therefore, we arrive at(65)2δ−κ≤X≤Y≤n−2δ.
Together withX+Y=n−κ and (62), it leads to(66)m=EGX∪S+EGY∪S−EGS≤14X+S2+14Y+S2−EGSby62≤14X+S2+14Y+S2=X+Y+S2+S24−X⋅Y2≤n2+κ24−2δ−κn−2δ2by65=δ2+14n−2δ+κ2≤δ2+14n−2δ+k−12,byκ≤k−1.
Combining this with (61), we have m=δ2+⌊1/4n−2δ+k−12⌋, and so S=κ=k−1, X=2δ−k+1, Y=n−2δ, EGS=0, EGX∪S=δ2, and EGY∪S=⌊1/4n−2δ+k−12⌋. Therefore, GS=Kk−1¯, GX∪S=Kδ,δ, and GY∪S=K⌊n−2δ+k−1/2⌋,⌈n−2δ+k−1/2⌉. This completes the proof.Theorem 17.
LetG be a connected triangle-free graph of order n and minimum degree δ≥k≥2. If(67)ρG≥δ−12+214n−2δ+k−12−δn−2δ+δ+124,then G is k-connected.Proof.
On the contrary, suppose thatκG<k. Since G is connected, by (67) and Lemma 1, we have(68)214n−2δ+k−12−δn−2δ+δ+124≤ρG−δ−12≤2EG−δn+δ+124,which yields(69)EG≥δ2+14n−2δ+k−12.
By Theorem16, VG=X∪S∪Y and S is a minimum vertex-cut of G with GS=Kk−1¯, GX∪S=Kδ,δ, and GY∪S=K⌊n−2δ+k−1/2⌋,⌈n−2δ+k−1/2⌉.
SinceEG=δ2+⌊1/4n−2δ+k−12⌋, the equalities hold in (68). Thus, by Lemma 1, G is either a regular graph or a bidegreed graph in which each vertex is of degree δ or n−1. However, G is neither a regular graph nor the complete bipartite graph K1,n−1, which yields a contradiction. Hence, G is k-connected.
By settingk=δ in Theorems 16 and 17, we obtain the two following theorems.Theorem 18.
LetG be a connected triangle-free graph of order n, size m, and minimum degree δ≥2. If(70)m≥δ2+14n−δ−12,then G is maximally connected, unless VG=X∪S∪Y, and S is a minimum vertex-cut of G with GS=Kδ−1¯, GX∪S=Kδ,δ, and GY∪S=K⌊n−δ−1/2⌋,⌈n−δ−1/2⌉.Theorem 19.
LetG be a connected triangle-free graph of order n and minimum degree δ≥2. If(71)ρG≥δ−12+214n−δ−12−δn−2δ+δ+124,then G is maximally connected.For super-connected graphs, we have the following results.Theorem 20.
LetG be a connected triangle-free graph of order n, size m, and minimum degree δ≥2. If(72)m≥δ2+14n−δ2,thenGis super-κ.Proof.
Letκ=κG. On the contrary, suppose that G is not super-κ. Since m≥δ2+⌊1/4n−δ2⌋, by Theorem 18, κ=δ. Let S be a minimum vertex-cut of G with δ vertices, and let X,Y1,…,Yp−1 (p≥2) denote the vertex-sets of the components of G−S, where 2≤X≤Y1≤⋯≤Yp−1. Set Y=∪i=1p−1Yi; then Y≥X≥2. Therefore, with the same proceeding of the proof of Theorem 16 (from (62) to (65)), we arrive at(73)δ≤X≤Y≤n−2δ.
Together withX+Y=n−δ and (62), it leads to(74)m=EGX∪S+EGY∪S−EGS≤14X+S2+14Y+S2−EGS≤14X+S2+14Y+S2=X+Y+S2+S24−X⋅Y2≤n2+δ24−δn−2δ2=δ2+14n−δ2.
Combining this with (72), we have m=δ2+⌊1/4n−δ2⌋, and so X=S=δ, Y=n−2δ, EGS=0, EGX∪S=δ2, and EGY∪S=⌊1/4n−δ2⌋. Therefore, GS=Kδ¯, GX∪S=Kδ,δ, and GY∪S=K⌊n−δ/2⌋,⌈n−δ/2⌉. Thus, GX=Kδ¯, which contradicts the fact that GX is a component of G with at least two vertices. The result follows.Theorem 21.
LetG be a connected triangle-free graph of order n and minimum degree δ≥2. If(75)ρG≥δ−12+214n−δ2−δn−2δ+δ+124,thenGis super-κ.Proof.
SinceG is connected, by (75) and Lemma 1, we have(76)214n−δ2−δn−2δ+δ+124≤ρG−δ−12≤2EG−δn+δ+124,which yields(77)EG≥δ2+14n−δ2.
By Theorem20, G is super-κ.Remark 4.
The lower bound onm given in Theorem 20 is sharp. For example, let n=3δ+3, VG=X∪S∪Y, GX=K1,δ, GY=K1,δ+1, and S is a minimum vertex-cut of G with GS=Kδ¯, GX∪S=Kδ,δ+1, and GY∪S=Kδ+1,δ+1. It is easy to check that(78)EG=δδ+1+δ+12=δ2+14n−δ2−1.
However,G−S=K1,δ∪K1,δ+1, which yields that G is not super-connected.



---

*Source: 5588146-2021-02-22.xml*