betaFeedback

WorksMathematics

Graphs attaining Haemers' toughness bound

Abstract

Haemers \cite{Haemers2020} conjectured that every connected noncomplete graph GG satisfies t(G)⩾μ2/(μn−δ)t(G)\geqslantμ_2/(μ_n-δ), where t(G)t(G) is the toughness of GG, μ2μ_2 and μnμ_n are its algebraic connectivity and Laplacian spectral radius, and δδ is its minimum degree. Greaves and Zhu \cite{GreavesZhu2026} recently proved this conjecture, leaving the equality case open. We characterize all graphs attaining equality: a graph attains equality if and only if its complement has a complete component whose order is at least the Laplacian spectral radius of every other component. Equivalently, its algebraic connectivity and independence number sum to its order. We also determine all vertex cuts attaining the toughness, and show that for regular graphs, the equality graphs are exactly the complete multipartite graphs with parts of equal size.

Introduction

Toughness and Laplacian bounds

All graphs in this paper are finite, simple, and undirected. For a graph G=(V,E)G=(V,E) and a subset U⊆VU\subseteq V, let G[U]G[U] denote the subgraph induced by UU. For S⊆VS\subseteq V, write G−S=G[V∖S]G-S=G[V\setminus S], and let c(G−S)c(G-S) be the number of connected components of G−SG-S. A set SS is a vertex cut if c(G−S)≥2c(G-S)\geq2, and the vertex connectivity κ(G)\kappa(G) of a noncomplete graph GG is the minimum cardinality among all vertex cuts of GG. The toughness of a connected noncomplete graph GG is

t(G)=min⁡{∣S∣c(G−S):S⊆V, c(G−S)≥2},(1)t(G)=\min\left\{\frac{|S|}{c(G-S)}:S\subseteq V,\ c(G-S)\geq2\right\}, \tag*{(1)}

and a complete graph has infinite toughness by convention. A vertex cut attaining the minimum in (1) is called a toughness cut.

Chvátal [5] introduced toughness in his study of Hamiltonian graphs. While vertex connectivity is determined by the minimum size of a vertex cut, toughness counts the number of components resulting from vertex deletion. If CC is a Hamiltonian cycle of GG and SS is a nonempty vertex set, then C−SC-S is a spanning subgraph of G−SG-S with at most ∣S∣|S| components. Hence every Hamiltonian graph is 11-tough, that is, t(G)≥1t(G)\geq1. Toughness has since been studied in connection with Hamiltonicity, factors, matchings, and spanning trees; see the survey of Bauer, Broersma, and Schmeichel [2].

Spectral bounds control toughness without examining individual vertex cuts. Alon [1] and Brouwer [3] initiated this approach for regular graphs. For a connected kk-regular graph GG, let λ\lambda be the largest absolute value of an adjacency eigenvalue other than kk. Brouwer proved that t(G)>k/λ−2t(G)>k/\lambda-2 and conjectured that t(G)≥k/λ−1t(G)\geq k/\lambda-1; Gu [10] proved this conjecture. Cioabă and Wong [7] and Cioabă and Gu [6] further developed the relations among the adjacency spectrum, toughness, and other connectivity parameters.

For irregular graphs, the Laplacian matrix L(G)=D(G)−A(G)L(G) = D(G) - A(G) provides a natural framework for spectral analysis, where A(G)A(G) is the adjacency matrix of GG and D(G)D(G) is the diagonal matrix of its vertex degrees. For a graph of order nn, the Laplacian eigenvalues of GG are denoted by

0=μ1(G)≤μ2(G)≤⋯≤μn(G),0 = \mu_1(G) \le\mu_2(G) \le\cdots\le\mu_n(G),

and we omit the argument GG when the graph is clear from the context. The eigenvalue μ2\mu_2 is the algebraic connectivity introduced by Fiedler [8], and δ=δ(G)\delta= \delta(G) denotes the minimum degree. Gu and Haemers [11] proved that every connected noncomplete graph GG of order nn satisfies

t(G)≥μnμ2n(μn−δ)(2)t(G) \ge\frac{\mu_n\mu_2}{n(\mu_n-\delta)} \tag*{(2)}
t(G)≥μ2μn−μ2(3)t(G) \ge\frac{\mu_2}{\mu_n-\mu_2} \tag*{(3)}

and Huang, Das, and Zhu [13] characterized the graphs attaining equality in each of these bounds.

Haemers [12] (see also [11 Conjecture 2.1]) conjectured the stronger inequality

t(G)≥μ2μn−δ.(4)t(G) \ge\frac{\mu_2}{\mu_n-\delta}. \tag*{(4)}

Since μ2≤δ\mu_2 \le\delta and μn≤n\mu_n \le n (Lemma 2.3), inequality (4) implies both (2) and (3). Greaves and Zhu [9] proved (4), leaving the characterization of the graphs attaining equality open. As noted by Gu and Haemers [11], every complete multipartite graph with a part of size at least two attains equality in (4). Greaves and Zhu [9] further exhibited noncomplete multipartite equality graphs obtained by adding edges within certain parts other than a largest part. These constructions are subsumed by Example 6.2 and Proposition 6.1 below. In this paper, we characterize all graphs attaining equality.

Main results

Let G‾\overline{G} denote the complement of GG, KmK_m the complete graph on mm vertices, and F1⊔F2F_1 \sqcup F_2 the disjoint union of F1F_1 and F2F_2. The join F1∨F2F_1 \vee F_2 is defined as the disjoint union F1⊔F2F_1 \sqcup F_2 together with all edges joining V(F1)V(F_1) and V(F2)V(F_2). The Laplacian spectral radius ρL(F)\rho_L(F) of a nonempty graph FF is the largest eigenvalue of L(F)L(F), thus ρL(F)=0\rho_L(F) = 0 if and only if FF has no edges. Finally, α(G)\alpha(G) denotes the independence number of GG, the maximum size of a set of pairwise nonadjacent vertices.

Theorem 1.1. Let GG be a connected noncomplete graph of order nn with minimum degree δ\delta and Laplacian eigenvalues 0=μ1<μ2≤⋯≤μn0 = \mu_1 < \mu_2 \le\cdots\le\mu_n. The following statements are equivalent.

(i) t(G)=μ2/(μn−δ)t(G) = \mu_2/(\mu_n - \delta).

(ii) μ2+α(G)=n\mu_2 + \alpha(G) = n.

(iii) There exist an integer m≥2m \ge2 and a graph FF with at least one vertex such that G‾≅Km⊔F\overline{G} \cong K_m \sqcup F and ρL(F)≤m\rho_L(F) \le m.

If these statements hold, then the integer mm in (iii) equals α(G)\alpha(G), and

μ2=δ=n−m,μn=n,t(G)=n−mm.(5)\mu_2 = \delta= n - m,\qquad\mu_n = n,\qquad t(G) = \frac{n-m}{m}. \tag*{(5)}

We call a connected noncomplete graph an equality graph if it attains equality in (4).

The three conditions in Theorem 1.1 describe equality from complementary points of view. Condition (ii) is the equality case of the chain

μ2≤δ≤n−α(G),(6)\mu_2 \le\delta\le n-\alpha(G), \tag*{(6)}

which holds for every connected noncomplete graph: the first inequality is part of Lemma 2.3, and the second holds because a vertex in a maximum independent set has all its neighbors outside that set. Condition (iii) is structural. It states that G≅K‾m∨HG \cong\overline{K}_m \vee H with H=F‾H=\overline{F}: the graph GG contains an independent set of size mm whose vertices are adjacent to all other vertices, and the remaining part HH is constrained only through the Laplacian spectral radius of its complement. In particular, the components of FF need not be complete, and their orders are not bounded in terms of mm (Examples 6.4 and 6.5).

Regularity removes this freedom. For positive integers n1,…,nrn_1,\ldots,n_r, the complete multipartite graph Kn1,…,nrK_{n_1,\ldots,n_r} has independent parts of sizes n1,…,nrn_1,\ldots,n_r and all edges between distinct parts.

Corollary 1.2. A connected noncomplete regular graph is an equality graph if and only if it is a complete multipartite graph whose parts have equal size, that is, Km,…,mK_{m,\ldots,m} with rr parts for some r,m≥2r,m\ge2. Its toughness is then r−1r-1.

The proof of Theorem 1.1 also determines all toughness cuts of an equality graph: they are exactly the complements of its maximum independent sets, or equivalently, the complements of the components of G‾\overline{G} isomorphic to Kα(G)K_{\alpha(G)} (Theorem 5.1). Consequently, every equality graph satisfies μ2(G)=κ(G)=δ(G)\mu_2(G)=\kappa(G)=\delta(G), and each of its toughness cuts is a minimum vertex cut (Corollary 5.2). Fiedler [8] proved that μ2(G)≤κ(G)\mu_2(G)\le\kappa(G) for every noncomplete graph, and Kirkland, Molitierno, Neumann, and Shader [14] characterized the graphs attaining equality; every equality graph for (4) therefore belongs to the class they describe. A minimum vertex cut of an equality graph need not be a toughness cut (Example 5.3).

Finally, (4) is the strongest of the three bounds, so equality in (2) or in (3) implies equality in (4). Theorem 1.1 yields the converse: every equality graph satisfies μ2=δ\mu_2=\delta and μn=n\mu_n=n, and hence attains equality in all three bounds (Corollary 4.2). Thus the three bounds have the same equality cases, and Theorem 1.1(iii) is an equivalent form of the equality family found by Huang, Das, and Zhu [13 Theorem 1.3]; see § 9.1.

Outline of the proof

Fix a vertex cut SS, let H1,…,HcH_1,\ldots,H_c be the components of G−SG-S, and let rir_i be the average number of neighbors in SS of a vertex of HiH_i. Compressing L(G)L(G) onto the span of the characteristic vectors of V(H1),…,V(Hc)V(H_1),\ldots,V(H_c) and SS yields two inequalities. The first, which uses μn\mu_n, gives ∣S∣(μn−δ)≥r1+⋯+rc|S|(\mu_n-\delta)\ge r_1+\cdots+r_c (Lemma 3.1). The second, which uses μ2\mu_2, shows that at most one rir_i is smaller than μ2\mu_2 (Lemma 3.2). The key step is Proposition 3.3: if some rir_i is smaller than μ2\mu_2, then the ratio ∣S∣/c|S|/c is strictly larger than μ2/(μn−δ)\mu_2/(\mu_n-\delta). Therefore a cut attaining equality has ri=μ2r_i=\mu_2 for every ii, and the equality cases of Lemma 3.1 force every HiH_i to be a single vertex of degree δ=μ2\delta=\mu_2 (Proposition 3.4).

Now let SS be a toughness cut of an equality graph. The vertices outside SS form an independent set, and each of them has degree μ2\mu_2. A Rayleigh quotient argument shows that they have a common neighborhood (Lemma 2.4), and the minimality of SS forces this neighborhood to be all of SS (Lemma 4.1). This gives the decomposition of G‾\overline{G} in Theorem 1.1(iii). Since the argument applies to every toughness cut, it determines all of them.

The paper is organized as follows. In § 2 we collect the Laplacian facts used in the proofs. In § 6 we prove the vertex-cut inequality together with its equality case. In Section 4 we prove Theorem 1.1 and compares the equality cases of the three bounds. In Section 5 we treat regular graphs and toughness cuts. In Section 6 we present constructions, the equality graphs with independence number two or three, and a recognition criterion.

Laplacian preliminaries

For a vertex vv of a graph FF, we write dF(v)d_F(v) for its degree, NF(v)N_F(v) for its neighborhood, and NF[v]=NF(v)∪{v}N_F[v]=N_F(v)\cup\{v\} for its closed neighborhood. For disjoint vertex sets UU and WW, let eF(U,W)e_F(U,W) be the number of edges with one end in UU and the other in WW. The maximum degree of FF is Δ(F)\Delta(F). We omit the subscript FF when the graph is clear from the context.

Vectors are real column vectors indexed by the vertices of the graph under consideration. We write 1\mathbf{1} for the all-ones vector, J=11TJ=\mathbf{1}\mathbf{1}^{\mathsf{T}} for the all-ones matrix, ev\mathbf{e}_v for the coordinate vector of a vertex vv, and χ(U)\boldsymbol{\chi}(U) for the characteristic vector of a vertex set UU. The identity matrix is II, with its order determined by the context. For every vector xx,

xTL(F)x=∑uv∈E(F)(xu−xv)2.(7)x^{\mathsf{T}}L(F)x=\sum_{uv\in E(F)}(x_u-x_v)^2. \tag*{(7)}

Hence L(F)L(F) is positive semidefinite, and its kernel consists of the vectors that are constant on each connected component of FF. For a graph GG of order nn,

μ2(G)=min⁡x≠0x⊥1xTL(G)xxTx,μn(G)=max⁡x≠0xTL(G)xxTx.(8)\mu_2(G)=\min_{\substack{x\ne0\\x\perp\mathbf{1}}}\frac{x^{\mathsf{T}}L(G)x}{x^{\mathsf{T}}x},\qquad \mu_n(G)=\max_{x\ne0}\frac{x^{\mathsf{T}}L(G)x}{x^{\mathsf{T}}x}. \tag*{(8)}

Expanding in an orthonormal eigenbasis of L(G)L(G) shows that every nonzero vector x⊥1x\perp\mathbf{1} attaining the minimum in (2.2) is a μ2(G)\mu_2(G)-eigenvector.

These facts are standard; see Fiedler [8] and Brouwer and Haemers [4]. We include short proofs of the consequences below because their equality cases are used later.

Lemma 2.1. Let FF be a graph of order q≥2q\ge2. Then

L(F)+L(F‾)=qI−Jandμ2(F)=q−ρL(F‾).(9)L(F)+L(\overline{F})=qI-J\qquad\text{and}\qquad\mu_2(F)=q-\rho_L(\overline{F}). \tag*{(9)}

Moreover, ρL(F‾)≤q\rho_L(\overline{F})\le q, with equality if and only if F‾\overline{F} is disconnected.

Proof. The matrix identity follows by comparing diagonal and off-diagonal entries. Both Laplacian matrices annihilate 1\mathbf{1}, and on 1⊥\mathbf{1}^{\perp} their sum acts as qIqI. Hence the eigenvalues of L(F‾)L(\overline{F}) on 1⊥\mathbf{1}^{\perp} are q−μi(F)q-\mu_i(F) for 2≤i≤q2\le i\le q, and the largest of them is q−μ2(F)≥0q-\mu_2(F)\ge0. The remaining eigenvalue of L(F‾)L(\overline{F}), on span⁡{1}\operatorname{span}\{\mathbf{1}\}, is zero, so ρL(F‾)=q−μ2(F)\rho_L(\overline{F})=q-\mu_2(F).

Since L(F‾)L(\overline{F}) is positive semidefinite, every eigenvalue of L(F‾)L(\overline{F}) on 1⊥\mathbf{1}^{\perp} is at most qq, and equality occurs if and only if L(F‾)L(\overline{F}) has a nonzero null vector orthogonal to 1\mathbf{1}. By (2.1), this happens if and only if F‾\overline{F} has at least two connected components. □

Lemma 2.2. Let FF be a graph with at least one edge. Then

Δ(F)+1≤ρL(F)≤2Δ(F).(10)\Delta(F)+1\le\rho_L(F)\le2\Delta(F). \tag*{(10)}

More generally, ρL(F)≥dF(v)+1\rho_L(F)\ge d_F(v)+1 for every vertex vv of positive degree, and this inequality is strict if some edge joins NF(v)N_F(v) to V(F)∖NF[v]V(F)\setminus N_F[v].

Proof. Fix a vertex vv of positive degree d=dF(v)d=d_F(v). Define xx by xv=dx_v=d, xu=−1x_u=-1 for u∈NF(v)u\in N_F(v), and xw=0x_w=0 for all other vertices ww. Then xTx=d(d+1)x^{\mathsf{T}}x=d(d+1), and (2.1) gives

xTL(F)x=d(d+1)2+eF(NF(v),V(F)∖NF[v]).x^{\mathsf{T}}L(F)x=d(d+1)^2+e_F\bigl(N_F(v),V(F)\setminus N_F[v]\bigr).

@page 4/14 starts_mid=1 ends_mid=1 Section 4 we prove Theorem 1.1 and compares the equality cases of the three bounds. In Section 5 we treat regular graphs and toughness cuts. In Section 6 we present constructions, the equality graphs with independence number two or three, and a recognition criterion.

Laplacian preliminaries {#sec:2}

For a vertex vv of a graph FF, we write dF(v)d_F(v) for its degree, NF(v)N_F(v) for its neighborhood, and NF[v]=NF(v)∪{v}N_F[v]=N_F(v)\cup\{v\} for its closed neighborhood. For disjoint vertex sets UU and WW, let eF(U,W)e_F(U,W) be the number of edges with one end in UU and the other in WW. The maximum degree of FF is Δ(F)\Delta(F). We omit the subscript FF when the graph is clear from the context.

Vectors are real column vectors indexed by the vertices of the graph under consideration. We write 1\mathbf{1} for the all-ones vector, J=11TJ=\mathbf{1}\mathbf{1}^{\mathsf{T}} for the all-ones matrix, ev\mathbf{e}_v for the coordinate vector of a vertex vv, and χ(U)\boldsymbol{\chi}(U) for the characteristic vector of a vertex set UU. The identity matrix is II, with its order determined by the context. For every vector xx,

xTL(F)x=∑uv∈E(F)(xu−xv)2(11)x^{\mathsf{T}}L(F)x=\sum_{uv\in E(F)}(x_u-x_v)^2 \tag*{(11)}

Hence L(F)L(F) is positive semidefinite, and its kernel consists of the vectors that are constant on each connected component of FF. For a graph GG of order nn,

μ2(G)=min⁡x≠0x⊥1xTL(G)xxTx,μn(G)=max⁡x≠0xTL(G)xxTx(12)\mu_2(G)=\min_{\substack{x\ne0\\x\perp\mathbf{1}}}\frac{x^{\mathsf{T}}L(G)x}{x^{\mathsf{T}}x},\qquad \mu_n(G)=\max_{x\ne0}\frac{x^{\mathsf{T}}L(G)x}{x^{\mathsf{T}}x} \tag*{(12)}

Expanding in an orthonormal eigenbasis of L(G)L(G) shows that every nonzero vector x⊥1x\perp\mathbf{1} attaining the minimum in (2.2) is a μ2(G)\mu_2(G)-eigenvector.

These facts are standard; see Fiedler [8] and Brouwer and Haemers [4]. We include short proofs of the consequences below because their equality cases are used later.

Lemma 2.1. Let FF be a graph of order q≥2q\ge2. Then

L(F)+L(F‾)=qI−Jandμ2(F)=q−ρL(F‾)(13)L(F)+L(\overline{F})=qI-J\qquad\text{and}\qquad\mu_2(F)=q-\rho_L(\overline{F}) \tag*{(13)}

Moreover, ρL(F‾)≤q\rho_L(\overline{F})\le q, with equality if and only if F‾\overline{F} is disconnected.

Proof. The matrix identity follows by comparing diagonal and off-diagonal entries. Both Laplacian matrices annihilate 1\mathbf{1}, and on 1⊥\mathbf{1}^{\perp} their sum acts as qIqI. Hence the eigenvalues of L(F‾)L(\overline{F}) on 1⊥\mathbf{1}^{\perp} are q−μi(F)q-\mu_i(F) for 2≤i≤q2\le i\le q, and the largest of them is q−μ2(F)≥0q-\mu_2(F)\ge0. The remaining eigenvalue of L(F‾)L(\overline{F}), on span⁡{1}\operatorname{span}\{\mathbf{1}\}, is zero, so ρL(F‾)=q−μ2(F)\rho_L(\overline{F})=q-\mu_2(F).

Since L(F‾)L(\overline{F}) is positive semidefinite, every eigenvalue of L(F‾)L(\overline{F}) on 1⊥\mathbf{1}^{\perp} is at most qq, and equality occurs if and only if L(F‾)L(\overline{F}) has a nonzero null vector orthogonal to 1\mathbf{1}. By (2.1), this happens if and only if F‾\overline{F} has at least two connected components. □

Lemma 2.2. Let FF be a graph with at least one edge. Then

Δ(F)+1≤ρL(F)≤2Δ(F)(14)\Delta(F)+1\le\rho_L(F)\le2\Delta(F) \tag*{(14)}

More generally, ρL(F)≥dF(v)+1\rho_L(F)\ge d_F(v)+1 for every vertex vv of positive degree, and this inequality is strict if some edge joins NF(v)N_F(v) to V(F)∖NF[v]V(F)\setminus N_F[v].

Proof. Fix a vertex vv of positive degree d=dF(v)d=d_F(v). Define xx by xv=dx_v=d, xu=−1x_u=-1 for u∈NF(v)u\in N_F(v), and xw=0x_w=0 for all other vertices ww. Then xTx=d(d+1)x^{\mathsf{T}}x=d(d+1), and (2.1) gives

xTL(F)x=d(d+1)2+eF(NF(v),V(F)∖NF[v]).x^{\mathsf{T}}L(F)x=d(d+1)^2+e_F\bigl(N_F(v),V(F)\setminus N_F[v]\bigr).

@page 4/14 starts_mid=1 ends_mid=1 Section 4 we prove Theorem 1.1 and compares the equality cases of the three bounds. In Section 5 we treat regular graphs and toughness cuts. In Section 6 we present constructions, the equality graphs with independence number two or three, and a recognition criterion.

Laplacian preliminaries {#sec:2}

For a vertex vv of a graph FF, we write dF(v)d_F(v) for its degree, NF(v)N_F(v) for its neighborhood, and NF[v]=NF(v)∪{v}N_F[v]=N_F(v)\cup\{v\} for its closed neighborhood. For disjoint vertex sets UU and WW, let eF(U,W)e_F(U,W) be the number of edges with one end in UU and the other in WW. The maximum degree of FF is Δ(F)\Delta(F). We omit the subscript FF when the graph is clear from the context.

Vectors are real column vectors indexed by the vertices of the graph under consideration. We write 1\mathbf{1} for the all-ones vector, J=11TJ=\mathbf{1}\mathbf{1}^{\mathsf{T}} for the all-ones matrix, ev\mathbf{e}_v for the coordinate vector of a vertex vv, and χ(U)\boldsymbol{\chi}(U) for the characteristic vector of a vertex set UU. The identity matrix is II, with its order determined by the context. For every vector xx,

xTL(F)x=∑uv∈E(F)(xu−xv)2(15)x^{\mathsf{T}}L(F)x=\sum_{uv\in E(F)}(x_u-x_v)^2 \tag*{(15)}

Hence L(F)L(F) is positive semidefinite, and its kernel consists of the vectors that are constant on each connected component of FF. For a graph GG of order nn,

μ2(G)=min⁡x≠0x⊥1xTL(G)xxTx,μn(G)=max⁡x≠0xTL(G)xxTx(16)\mu_2(G)=\min_{\substack{x\ne0\\x\perp\mathbf{1}}}\frac{x^{\mathsf{T}}L(G)x}{x^{\mathsf{T}}x},\qquad \mu_n(G)=\max_{x\ne0}\frac{x^{\mathsf{T}}L(G)x}{x^{\mathsf{T}}x} \tag*{(16)}

Expanding in an orthonormal eigenbasis of L(G)L(G) shows that every nonzero vector x⊥1x\perp\mathbf{1} attaining the minimum in (2.2) is a μ2(G)\mu_2(G)-eigenvector.

These facts are standard; see Fiedler [8] and Brouwer and Haemers [4]. We include short proofs of the consequences below because their equality cases are used later.

Lemma 2.1. Let FF be a graph of order q≥2q\ge2. Then

L(F)+L(F‾)=qI−Jandμ2(F)=q−ρL(F‾)(17)L(F)+L(\overline{F})=qI-J\qquad\text{and}\qquad\mu_2(F)=q-\rho_L(\overline{F}) \tag*{(17)}

Moreover, ρL(F‾)≤q\rho_L(\overline{F})\le q, with equality if and only if F‾\overline{F} is disconnected.

Proof. The matrix identity follows by comparing diagonal and off-diagonal entries. Both Laplacian matrices annihilate 1\mathbf{1}, and on 1⊥\mathbf{1}^{\perp} their sum acts as qIqI. Hence the eigenvalues of L(F‾)L(\overline{F}) on 1⊥\mathbf{1}^{\perp} are q−μi(F)q-\mu_i(F) for 2≤i≤q2\le i\le q, and the largest of them is q−μ2(F)≥0q-\mu_2(F)\ge0. The remaining eigenvalue of L(F‾)L(\overline{F}), on span⁡{1}\operatorname{span}\{\mathbf{1}\}, is zero, so ρL(F‾)=q−μ2(F)\rho_L(\overline{F})=q-\mu_2(F).

Since L(F‾)L(\overline{F}) is positive semidefinite, every eigenvalue of L(F‾)L(\overline{F}) on 1⊥\mathbf{1}^{\perp} is at most qq, and equality occurs if and only if L(F‾)L(\overline{F}) has a nonzero null vector orthogonal to 1\mathbf{1}. By (2.1), this happens if and only if F‾\overline{F} has at least two connected components. □

Lemma 2.2. Let FF be a graph with at least one edge. Then

Δ(F)+1≤ρL(F)≤2Δ(F)(18)\Delta(F)+1\le\rho_L(F)\le2\Delta(F) \tag*{(18)}

More generally, ρL(F)≥dF(v)+1\rho_L(F)\ge d_F(v)+1 for every vertex vv of positive degree, and this inequality is strict if some edge joins NF(v)N_F(v) to V(F)∖NF[v]V(F)\setminus N_F[v].

Proof. Fix a vertex vv of positive degree d=dF(v)d=d_F(v). Define xx by xv=dx_v=d, xu=−1x_u=-1 for u∈NF(v)u\in N_F(v), and xw=0x_w=0 for all other vertices ww. Then xTx=d(d+1)x^{\mathsf{T}}x=d(d+1), and (2.1) gives

xTL(F)x=d(d+1)2+eF(NF(v),V(F)∖NF[v]).x^{\mathsf{T}}L(F)x=d(d+1)^2+e_F\bigl(N_F(v),V(F)\setminus N_F[v]\bigr).

@page 4/14 starts_mid=1 ends_mid=1 Section 4 we prove Theorem 1.1 and compares the equality cases of the three bounds. In Section 5 we treat regular graphs and toughness cuts. In Section 6 we present constructions, the equality graphs with independence number two or three, and a recognition criterion.

Laplacian preliminaries {#sec:2}

For a vertex vv of a graph FF, we write dF(v)d_F(v) for its degree, NF(v)N_F(v) for its neighborhood, and NF[v]=NF(v)∪{v}N_F[v]=N_F(v)\cup\{v\} for its closed neighborhood. For disjoint vertex sets UU and WW, let eF(U,W)e_F(U,W) be the number of edges with one end in UU and the other in WW. The maximum degree of FF is Δ(F)\Delta(F). We omit the subscript FF when the graph is clear from the context.

Vectors are real column vectors indexed by the vertices of the graph under consideration. We write 1\mathbf{1} for the all-ones vector, J=11TJ=\mathbf{1}\mathbf{1}^{\mathsf{T}} for the all-ones matrix, ev\mathbf{e}_v for the coordinate vector of a vertex vv, and χ(U)\boldsymbol{\chi}(U) for the characteristic vector of a vertex set UU. The identity matrix is II, with its order determined by the context. For every vector xx,

xTL(F)x=∑uv∈E(F)(xu−xv)2(19)x^{\mathsf{T}}L(F)x=\sum_{uv\in E(F)}(x_u-x_v)^2 \tag*{(19)}

Hence L(F)L(F) is positive semidefinite, and its kernel consists of the vectors that are constant on each connected component of FF. For a graph GG of order nn,

μ2(G)=min⁡x≠0x⊥1xTL(G)xxTx,μn(G)=max⁡x≠0xTL(G)xxTx(20)\mu_2(G)=\min_{\substack{x\ne0\\x\perp\mathbf{1}}}\frac{x^{\mathsf{T}}L(G)x}{x^{\mathsf{T}}x},\qquad \mu_n(G)=\max_{x\ne0}\frac{x^{\mathsf{T}}L(G)x}{x^{\mathsf{T}}x} \tag*{(20)}

Expanding in an orthonormal eigenbasis of L(G)L(G) shows that every nonzero vector x⊥1x\perp\mathbf{1} attaining the minimum in (2.2) is a μ2(G)\mu_2(G)-eigenvector.

These facts are standard; see Fiedler [8] and Brouwer and Haemers [4]. We include short proofs of the consequences below because their equality cases are used later.

Lemma 2.1. Let FF be a graph of order q≥2q\ge2. Then

L(F)+L(F‾)=qI−Jandμ2(F)=q−ρL(F‾)(21)L(F)+L(\overline{F})=qI-J\qquad\text{and}\qquad\mu_2(F)=q-\rho_L(\overline{F}) \tag*{(21)}

Moreover, ρL(F‾)≤q\rho_L(\overline{F})\le q, with equality if and only if F‾\overline{F} is disconnected.

Proof. The matrix identity follows by comparing diagonal and off-diagonal entries. Both Laplacian matrices annihilate 1\mathbf{1}, and on 1⊥\mathbf{1}^{\perp} their sum acts as qIqI. Hence the eigenvalues of L(F‾)L(\overline{F}) on 1⊥\mathbf{1}^{\perp} are q−μi(F)q-\mu_i(F) for 2≤i≤q2\le i\le q, and the largest of them is q−μ2(F)≥0q-\mu_2(F)\ge0. The remaining eigenvalue of L(F‾)L(\overline{F}), on span⁡{1}\operatorname{span}\{\mathbf{1}\}, is zero, so ρL(F‾)=q−μ2(F)\rho_L(\overline{F})=q-\mu_2(F).

Since L(F‾)L(\overline{F}) is positive semidefinite, every eigenvalue of L(F‾)L(\overline{F}) on 1⊥\mathbf{1}^{\perp} is at most qq, and equality occurs if and only if L(F‾)L(\overline{F}) has a nonzero null vector orthogonal to 1\mathbf{1}. By (2.1), this happens if and only if F‾\overline{F} has at least two connected components. □

Lemma 2.2. Let FF be a graph with at least one edge. Then

Δ(F)+1≤ρL(F)≤2Δ(F)(22)\Delta(F)+1\le\rho_L(F)\le2\Delta(F) \tag*{(22)}

More generally, ρL(F)≥dF(v)+1\rho_L(F)\ge d_F(v)+1 for every vertex vv of positive degree, and this inequality is strict if some edge joins NF(v)N_F(v) to V(F)∖NF[v]V(F)\setminus N_F[v].

Proof. Fix a vertex vv of positive degree d=dF(v)d=d_F(v). Define xx by xv=dx_v=d, xu=−1x_u=-1 for u∈NF(v)u\in N_F(v), and xw=0x_w=0 for all other vertices ww. Then xTx=d(d+1)x^{\mathsf{T}}x=d(d+1), and (2.1) gives

xTL(F)x=d(d+1)2+eF(NF(v),V(F)∖NF[v]).(23)x^{\mathsf{T}}L(F)x=d(d+1)^2+e_F\bigl(N_F(v),V(F)\setminus N_F[v]\bigr). \tag*{(23)}

The lower bounds and the strictness assertion follow from the maximum Rayleigh quotient; for the first inequality in (2.4), choose vv of maximum degree. For the upper bound, (2.1) gives, for every xx,

xTL(F)x≤2∑uv∈E(F)(xu2+xv2)=2∑v∈V(F)dF(v)xv2≤2Δ(F)xTx.x^{\mathsf T}L(F)x \le2\sum_{uv\in E(F)}(x_u^2+x_v^2)=2\sum_{v\in V(F)}d_F(v)x_v^2\le2\Delta(F)x^{\mathsf T}x.

Taking the maximum Rayleigh quotient completes the proof. □

Lemma 2.3. Let GG be a connected noncomplete graph of order nn with minimum degree δ\delta. Then

0<μ2≤δ<μn−1≤n−1.(24)0<\mu_2\le\delta<\mu_n-1\le n-1. \tag*{(24)}

Moreover, μ2≤∣S∣\mu_2\le|S| for every vertex cut SS of GG; that is, μ2≤κ(G)\mu_2\le\kappa(G).

Proof. Since GG is connected, the kernel of L(G)L(G) is spanned by 1\mathbf{1}, and therefore μ2>0\mu_2>0.

Let SS be a vertex cut, and let UU and WW be the vertex sets of two distinct components of G−SG-S. Define xx to be ∣W∣|W| on UU, −∣U∣-|U| on WW, and 00 elsewhere. Then x≠0x\ne0 and x⊥1x\perp\mathbf{1}. By (2.1), only edges between U∪WU\cup W and SS contribute to xTL(G)xx^{\mathsf T}L(G)x, and every vertex of U∪WU\cup W has at most ∣S∣|S| neighbors in SS. Hence xTL(G)x≤∣S∣xTxx^{\mathsf T}L(G)x\le|S|x^{\mathsf T}x, and (2.2) gives μ2≤∣S∣\mu_2\le|S|.

Let vv be a vertex of degree δ\delta. Since GG is noncomplete, δ≤n−2\delta\le n-2. Deleting N(v)N(v) therefore isolates vv and leaves at least one further vertex, so N(v)N(v) is a vertex cut and μ2≤δ\mu_2\le\delta. Since GG is connected and V(G)∖N[v]V(G)\setminus N[v] is nonempty, some edge joins N(v)N(v) to V(G)∖N[v]V(G)\setminus N[v], and Lemma 2.2 gives μn>δ+1\mu_n>\delta+1. Finally, μn≤n\mu_n\le n by Lemma 2.1. □

Lemma 2.4. Let GG be a connected graph, and let uu and vv be distinct nonadjacent vertices with dG(u)=dG(v)=μ2(G)d_G(u)=d_G(v)=\mu_2(G). Then NG(u)=NG(v)N_G(u)=N_G(v).

Proof. The vector x=eu−evx=e_u-e_v is orthogonal to 1\mathbf{1}. Since uu and vv are not adjacent,

xTL(G)xxTx=dG(u)+dG(v)2=μ2(G).\frac{x^{\mathsf T}L(G)x}{x^{\mathsf T}x}=\frac{d_G(u)+d_G(v)}{2}=\mu_2(G).

Thus xx attains the minimum in (2.2), and L(G)x=μ2(G)xL(G)x=\mu_2(G)x. At a vertex w∉{u,v}w\notin\{u,v\}, this equation reads −A(G)wu+A(G)wv=0-A(G)_{wu}+A(G)_{wv}=0. Hence every such ww is adjacent to uu if and only if it is adjacent to vv. □

Vertex cuts and the equality case

Throughout this section, GG is a connected noncomplete graph of order nn with minimum degree δ\delta and Laplacian eigenvalues 0=μ1<μ2≤⋯≤μn0=\mu_1<\mu_2\le\cdots\le\mu_n. Fix a vertex cut SS, let H1,…,HcH_1,\ldots,H_c be the components of G−SG-S, where c=c(G−S)≥2c=c(G-S)\ge2, and set

hi=∣V(Hi)∣,ri=eG(V(Hi),S)hi(1≤i≤c).(25)h_i=|V(H_i)|,\qquad r_i=\frac{e_G(V(H_i),S)}{h_i}\qquad(1\le i\le c). \tag*{(25)}

Thus rir_i is the average number of neighbors in SS of a vertex of HiH_i. Since GG is connected, ri>0r_i>0. A vertex of HiH_i has at most hi−1h_i-1 neighbors outside SS, so

ri≥δ−hi+1.(26)r_i\ge\delta-h_i+1. \tag*{(26)}

Lemmas 3.1 and 3.2 are the compression inequalities underlying the proof of Greaves and Zhu [9 Lemmas 2.3 and 2.4]; we derive them in a form that displays their equality cases. The new ingredient is Proposition 3.3, which shows that a component with ri<μ2r_i<\mu_2 forces strict inequality.

Let TT be the n×(c+1)n \times(c+1) matrix whose iith column is χ(V(Hi))/hi\chi(V(H_i))/\sqrt{h_i} for 1≤i≤c1 \le i \le c and whose last column is χ(S)/∣S∣\chi(S)/\sqrt{|S|}. These columns are orthonormal, and a direct computation shows that the compression Q=TTL(G)TQ = T^{T}L(G)T is

Q=(r1−r1h1/∣S∣⋱⋮rc−rchc/∣S∣−r1h1/∣S∣⋯−rchc/∣S∣1∣S∣∑i=1chiri)(27)Q = \begin{pmatrix} r_1 & & & -r_1\sqrt{h_1/|S|}\\ & \ddots& & \vdots\\ & & r_c & -r_c\sqrt{h_c/|S|}\\ -r_1\sqrt{h_1/|S|} & \cdots& -r_c\sqrt{h_c/|S|} & \frac{1}{|S|}\sum_{i=1}^{c}h_ir_i \end{pmatrix} \tag*{(27)}

The matrices μnI−L(G)\mu_n I-L(G) and L(G)−μ2I+(μ2/n)JL(G)-\mu_2 I+(\mu_2/n)J are positive semidefinite; the second vanishes on 11 and agrees with L(G)−μ2IL(G)-\mu_2 I on 1⊥1^\perp. Hence their compressions by TT are positive semidefinite as well.

Lemma 3.1. In the notation of (25), ri<μnr_i < \mu_n for every ii, and

∣S∣≥∑i=1chiriμn−ri.(28)|S| \ge\sum_{i=1}^{c}\frac{h_ir_i}{\mu_n-r_i}. \tag*{(28)}

Moreover, for every ii,

μn−ri≤μn−δ+hi−1≤(μn−δ)hi,(29)\mu_n-r_i \le\mu_n-\delta+h_i-1 \le(\mu_n-\delta)h_i, \tag*{(29)}

where the second inequality is strict if and only if hi≥2h_i \ge2. Consequently,

∣S∣(μn−δ)≥∑i=1cri.(30)|S|(\mu_n-\delta) \ge\sum_{i=1}^{c}r_i. \tag*{(30)}

Proof. The matrix μnI−Q\mu_n I-Q, which is the compression of μnI−L(G)\mu_n I-L(G) by TT, is positive semidefinite. For 1≤i≤c1 \le i \le c, its iith diagonal entry is μn−ri\mu_n-r_i, and its (i,c+1)(i,c+1) entry rihi/∣S∣r_i\sqrt{h_i/|S|} is nonzero. In a positive semidefinite matrix, a zero diagonal entry forces the corresponding row to vanish, as the principal 2×22 \times2 submatrices show. Hence μn−ri>0\mu_n-r_i>0.

The leading principal c×cc \times c submatrix of μnI−Q\mu_n I-Q is therefore diagonal and positive definite, and its Schur complement in μnI−Q\mu_n I-Q is nonnegative:

0≤μn−1∣S∣∑i=1chiri−1∣S∣∑i=1chiri2μn−ri=μn(1−1∣S∣∑i=1chiriμn−ri).0 \le\mu_n-\frac{1}{|S|}\sum_{i=1}^{c}h_ir_i-\frac{1}{|S|}\sum_{i=1}^{c}\frac{h_ir_i^2}{\mu_n-r_i} =\mu_n\left(1-\frac{1}{|S|}\sum_{i=1}^{c}\frac{h_ir_i}{\mu_n-r_i}\right).

This proves (28).

The first inequality in (29) is (26). For the second,

(μn−δ)hi−(μn−δ+hi−1)=(hi−1)(μn−δ−1).(\mu_n-\delta)h_i-(\mu_n-\delta+h_i-1)=(h_i-1)(\mu_n-\delta-1).

which is nonnegative, and positive if and only if hi≥2h_i \ge2, because μn−δ>1\mu_n-\delta>1 by Lemma 2.3. Finally, (29) gives hiri/(μn−ri)≥ri/(μn−δ)h_ir_i/(\mu_n-r_i) \ge r_i/(\mu_n-\delta) for every ii, and substituting these inequalities into (28) yields (30). □

Lemma 3.2. In the notation of (25), any two distinct indices ii and jj satisfy

(ri−μ2)hj+(rj−μ2)hi≥0.(31)(r_i-\mu_2)h_j+(r_j-\mu_2)h_i \ge0. \tag*{(31)}

In particular, at most one of r1,…,rcr_1,\ldots,r_c is smaller than μ2\mu_2. If r1<μ2r_1 < \mu_2, then rj>μ2r_j > \mu_2 for every 2≤j≤c2 \le j \le c, and

n+μ2∑j=2chjrj−μ2≤μ2h1μ2−r1.(32)n+\mu_2\sum_{j=2}^{c}\frac{h_j}{r_j-\mu_2}\le\frac{\mu_2h_1}{\mu_2-r_1}. \tag*{(32)}

Proof. The leading principal c×cc\times c submatrix of the compression of L(G)−μ2I+(μ2/n)JL(G)-\mu_2I+(\mu_2/n)J is

X=diag⁡(r1−μ2,…,rc−μ2)+μ2nuuT,u=(h1,…,hc)T,X=\operatorname{diag}(r_1-\mu_2,\ldots,r_c-\mu_2)+\frac{\mu_2}{n}uu^{\mathsf T},\qquad u=(\sqrt{h_1},\ldots,\sqrt{h_c})^{\mathsf T},

and it is positive semidefinite. For distinct ii and jj, evaluate its quadratic form at the vector with iith coordinate hj\sqrt{h_j}, jjth coordinate −hi-\sqrt{h_i}, and all other coordinates zero. This vector is orthogonal to uu, so the rank-one term vanishes, and (31) follows. The assertions about the signs of ri−μ2r_i-\mu_2 follow immediately.

Now suppose that r1<μ2r_1<\mu_2. Then every diagonal entry ri−μ2r_i-\mu_2 is nonzero, and exactly one of them is negative. By the determinant formula for a rank-one perturbation of a diagonal matrix,

det⁡X=∏i=1c(ri−μ2)(1+μ2n∑i=1chiri−μ2).\det X=\prod_{i=1}^{c}(r_i-\mu_2)\left(1+\frac{\mu_2}{n}\sum_{i=1}^{c}\frac{h_i}{r_i-\mu_2}\right).

Since det⁡X≥0\det X\ge0 and the product is negative, the factor in parentheses is nonpositive. Separating the term i=1i=1 and multiplying by nn gives (32). □

Proposition 3.3. In the notation of (25), if ri<μ2r_i<\mu_2 for some ii, then

∣S∣(μn−δ)>cμ2.(33)|S|(\mu_n-\delta)>c\mu_2. \tag*{(33)}

Proof. Renumber the components so that r1<μ2r_1<\mu_2, and put

a=μ2−r1>0,bj=rj−μ2(2≤j≤c).a=\mu_2-r_1>0,\qquad b_j=r_j-\mu_2\quad(2\le j\le c).

By Lemma 3.2, bj>0b_j>0 for every jj. Suppose, for a contradiction, that ∣S∣(μn−δ)≤cμ2|S|(\mu_n-\delta)\le c\mu_2. Combined with (30), this gives ∑i=1cri≤cμ2\sum_{i=1}^{c}r_i\le c\mu_2, that is,

a≥∑j=2cbj.(34)a\ge\sum_{j=2}^{c}b_j. \tag*{(34)}

In particular, a≥bja\ge b_j for every j≥2j\ge2.

Substitute n=∣S∣+∑i=1chin=|S|+\sum_{i=1}^{c}h_i into (32) and multiply by aa. Since μ2h1−ah1=r1h1\mu_2h_1-ah_1=r_1h_1 and 1+μ2/bj=rj/bj1+\mu_2/b_j=r_j/b_j, we obtain

h1r1≥a(∣S∣+∑j=2chjrjbj).(35)h_1r_1\ge a\left(|S|+\sum_{j=2}^{c}\frac{h_jr_j}{b_j}\right). \tag*{(35)}

On the other hand, multiplying (28) by μn−r1>0\mu_n-r_1>0 gives

∣S∣(μn−r1)≥h1r1+∑j=2chjrj(μn−r1)μn−rj.|S|(\mu_n-r_1)\ge h_1r_1+\sum_{j=2}^{c}\frac{h_jr_j(\mu_n-r_1)}{\mu_n-r_j}.

Insert (35) and subtract a∣S∣a|S| from both sides. Since μn−r1−a=μn−μ2\mu_n-r_1-a=\mu_n-\mu_2, this yields

∣S∣(μn−μ2)≥∑j=2chjrj(abj+μn−r1μn−rj).(36)|S|(\mu_n-\mu_2)\ge\sum_{j=2}^{c}h_jr_j\left(\frac{a}{b_j}+\frac{\mu_n-r_1}{\mu_n-r_j}\right). \tag*{(36)}

Using μn−r1=(μn−rj)+a+bj\mu_n-r_1=(\mu_n-r_j)+a+b_j, we rewrite each factor in parentheses as

abj+μn−r1μn−rj=1+abj+a+bjμn−rj=(1+abj)(1+bjμn−rj)=(1+abj)μn−μ2μn−rj.\frac{a}{b_j}+\frac{\mu_n-r_1}{\mu_n-r_j}=1+\frac{a}{b_j}+\frac{a+b_j}{\mu_n-r_j}=\left(1+\frac{a}{b_j}\right)\left(1+\frac{b_j}{\mu_n-r_j}\right)=\left(1+\frac{a}{b_j}\right)\frac{\mu_n-\mu_2}{\mu_n-r_j}.

Since μn−μ2>0\mu_n-\mu_2>0 by Lemma 2.3, dividing (36) by μn−μ2\mu_n-\mu_2 gives

∣S∣≥∑j=2chjrjμn−rj(1+abj).|S|\ge\sum_{j=2}^{c}\frac{h_jr_j}{\mu_n-r_j}\left(1+\frac{a}{b_j}\right).

By (29), hj/(μn−rj)≥1/(μn−δ)h_j/(\mu_n-r_j)\ge1/(\mu_n-\delta). Together with a≥bja\ge b_j, rj>μ2r_j>\mu_2, and c≥2c\ge2, this gives

∣S∣(μn−δ)≥∑j=2crj(1+abj)≥2∑j=2crj>2(c−1)μ2≥cμ2,|S|(\mu_n-\delta)\ge\sum_{j=2}^{c}r_j\left(1+\frac{a}{b_j}\right)\ge2\sum_{j=2}^{c}r_j>2(c-1)\mu_2\ge c\mu_2,

which contradicts the assumption. This proves (33).

The following proposition gives the cut inequality together with the constraints that equality imposes on every component.

Proposition 3.4. Every vertex cut SS of GG satisfies

∣S∣c(G−S)≥μ2μn−δ.(37)\frac{|S|}{c(G-S)}\ge\frac{\mu_2}{\mu_n-\delta}. \tag*{(37)}

If equality holds, then every component of G−SG-S is a single vertex of degree δ\delta, and μ2=δ\mu_2=\delta.

Proof. If ri<μ2r_i<\mu_2 for some ii, then Proposition 3.3 gives strict inequality in (37). Otherwise ri≥μ2r_i\ge\mu_2 for every ii, and (30) gives ∣S∣(μn−δ)≥∑i=1cri≥cμ2|S|(\mu_n-\delta)\ge\sum_{i=1}^{c}r_i\ge c\mu_2. This proves (37).

Suppose that equality holds. Then ri≥μ2r_i\ge\mu_2 for every ii by Proposition 3.3, and (28) and (29) give

cμ2=∣S∣(μn−δ)≥∑i=1c(μn−δ)hiriμn−ri≥∑i=1cri≥cμ2.c\mu_2=|S|(\mu_n-\delta)\ge\sum_{i=1}^{c}\frac{(\mu_n-\delta)h_ir_i}{\mu_n-r_i}\ge\sum_{i=1}^{c}r_i\ge c\mu_2.

Hence all these inequalities are equalities. The last one gives ri=μ2r_i=\mu_2 for every ii. Since ri>0r_i>0, the middle one gives μn−ri=(μn−δ)hi\mu_n-r_i=(\mu_n-\delta)h_i, so both inequalities in (29) are equalities. By Lemma 3.1, this forces hi=1h_i=1, and hence ri=δr_i=\delta, because δ−hi+1≤ri=μ2≤δ\delta-h_i+1\le r_i=\mu_2\le\delta. For a singleton component, rir_i is the degree of its vertex. Hence every component of G−SG-S is a single vertex of degree δ\delta, and μ2=ri=δ\mu_2=r_i=\delta.

Taking the minimum of (37) over all vertex cuts SS recovers (4). Moreover, Proposition 3.4 reduces the equality problem to vertex cuts SS such that V(G)∖SV(G)\setminus S is an independent set of vertices of degree μ2\mu_2.

The equality characterization

We first show that, in an equality graph, the vertices outside a toughness cut form an independent set joined to every vertex of the cut. The minimality of the toughness cut forces the common neighborhood given by Lemma 2.4 to be the whole cut.

Lemma 4.1. Let GG be an equality graph of order nn, and let SS be a toughness cut of GG. Then V(G)∖SV(G)\setminus S is a maximum independent set, every vertex of V(G)∖SV(G)\setminus S is adjacent to every vertex of SS, and

∣S∣=δ=μ2,∣V(G)∖S∣=n−δ,μn=n.(38)|S|=\delta=\mu_2,\qquad|V(G)\setminus S|=n-\delta,\qquad\mu_n=n. \tag*{(38)}

Proof. Put U=V(G)∖SU=V(G)\setminus S and m=∣U∣m=|U|. Since SS is a toughness cut, ∣S∣/c(G−S)=t(G)=μ2/(μn−δ)|S|/c(G-S)=t(G)=\mu_2/(\mu_n-\delta). By Proposition 3.4, every component of G−SG-S is a single vertex of degree δ\delta, and μ2=δ\mu_2=\delta. Thus UU is an independent set of vertices of degree δ\delta, c(G−S)=m≥2c(G-S)=m\ge2, and t(G)=∣S∣/mt(G)=|S|/m. By Lemma 2.4, the vertices of UU have a common neighborhood W⊆SW\subseteq S, and ∣W∣=δ|W|=\delta.

Suppose that S∖WS\setminus W is nonempty. Deleting WW isolates the mm vertices of UU, and the vertices of S∖WS\setminus W form at least one further component. Hence

t(G)≤∣W∣c(G−W)≤δm+1≤∣S∣m+1<∣S∣m=t(G),t(G)\le\frac{|W|}{c(G-W)}\le\frac{\delta}{m+1}\le\frac{|S|}{m+1}<\frac{|S|}{m}=t(G),

a contradiction. Therefore W=SW=S. Thus every vertex of UU is adjacent to every vertex of SS, ∣S∣=δ=μ2|S|=\delta=\mu_2, and m=n−δm=n-\delta.

The equality t(G)=μ2/(μn−δ)t(G)=\mu_2/(\mu_n-\delta) now reads δ/m=δ/(μn−δ)\delta/m=\delta/(\mu_n-\delta). Since δ>0\delta>0, we obtain μn=δ+m=n\mu_n=\delta+m=n. Finally, (6) gives α(G)≤n−δ=m\alpha(G)\le n-\delta=m, so the independent set UU is maximum. □

Proof of Theorem 1.1. (i) implies (ii) and (iii). Assume (i), let SS be a toughness cut, and put U=V(G)∖SU=V(G)\setminus S and m=n−δm=n-\delta. By Lemma 4.1, UU is a maximum independent set of size m≥2m\ge2, and every vertex of UU is adjacent to every vertex of SS. Hence G‾[U]≅Km\overline{G}[U]\cong K_m is a component of G‾\overline{G}, and

G‾≅Km⊔F,F=G‾[S].\overline{G}\cong K_m\sqcup F,\qquad F=\overline{G}[S].

where FF has ∣S∣=δ≥1|S|=\delta\ge1 vertices. By Lemma 2.1 and μ2=δ=n−m\mu_2=\delta=n-m, we have ρL(G‾)=n−μ2=m\rho_L(\overline{G})=n-\mu_2=m. Since L(G‾)L(\overline{G}) is block diagonal with blocks L(Km)L(K_m) and L(F)L(F), it follows that ρL(F)≤m\rho_L(F)\le m, which proves (iii). Moreover, α(G)=∣U∣=m=n−μ2\alpha(G)=|U|=m=n-\mu_2, which proves (ii).

(iii) implies (i). Assume (iii). Since ρL(Km)=m\rho_L(K_m)=m and ρL(F)≤m\rho_L(F)\le m, we have ρL(G‾)=m\rho_L(\overline{G})=m. As G‾\overline{G} is disconnected, Lemma 2.1 gives

μ2=n−mandμn=n.\mu_2=n-m\qquad\text{and}\qquad\mu_n=n.

The mm vertices corresponding to KmK_m have degree n−mn-m in GG, so δ≤n−m=μ2≤δ\delta\le n-m=\mu_2\le\delta, and hence δ=n−m\delta=n-m. Deleting the other n−mn-m vertices leaves m≥2m\ge2 isolated vertices, so

t(G)≤n−mm=μ2μn−δ.t(G)\le\frac{n-m}{m}=\frac{\mu_2}{\mu_n-\delta}.

The reverse inequality is Proposition 3.4. This proves (i) and (5). Finally, α(G)≤n−δ=m\alpha(G)\le n-\delta=m by (6), and the mm vertices corresponding to KmK_m form an independent set in GG; hence m=α(G)m=\alpha(G).

(ii) implies (iii). Assume (ii). By (6), μ2=δ=n−α(G)\mu_2=\delta=n-\alpha(G). Let UU be a maximum independent set, and put m=α(G)m=\alpha(G). Every vertex of UU has all its neighbors outside UU, so its degree is at most n−m=δn-m=\delta. Hence it has degree exactly δ\delta and is adjacent to every vertex outside UU. Therefore

G‾≅Km⊔F,F=G‾[V(G)∖U].\overline{G}\cong K_m\sqcup F,\qquad F=\overline{G}[V(G)\setminus U].

Here m≥2m\ge2 because GG is noncomplete, and FF has at least one vertex because GG is connected. As before, Lemma 2.1 gives ρL(G‾)=n−μ2=m\rho_L(\overline{G})=n-\mu_2=m, and hence ρL(F)≤m\rho_L(F)\le m. This proves (iii) and completes the proof. □

We now compare the equality cases of the three Laplacian bounds.

Corollary 4.2. For a connected noncomplete graph GG of order nn, the following three equalities are equivalent:

t(G)=μ2μn−δ,t(G)=μnμ2n(μn−δ),t(G)=μ2μn−μ2.t(G)=\frac{\mu_2}{\mu_n-\delta},\qquad t(G)=\frac{\mu_n\mu_2}{n(\mu_n-\delta)},\qquad t(G)=\frac{\mu_2}{\mu_n-\mu_2}.

In particular, the bounds (2), (3), and (4) have the same equality graphs, namely those described in Theorem 1.1.

Proof. By Lemma 2.3 and (4),

μnμ2n(μn−δ)≤μ2μn−δ≤t(G)andμ2μn−μ2≤μ2μn−δ≤t(G).\frac{\mu_n\mu_2}{n(\mu_n-\delta)}\leq\frac{\mu_2}{\mu_n-\delta}\leq t(G) \qquad\text{and}\qquad \frac{\mu_2}{\mu_n-\mu_2}\leq\frac{\mu_2}{\mu_n-\delta}\leq t(G).

Hence each of the last two equalities implies the first. Conversely, the first equality gives μn=n\mu_n=n and μ2=δ\mu_2=\delta by Theorem 1.1, and then the three ratios coincide. □

Remark 4.3. By Theorem 1.1, inequality (4) is strict whenever μ2<δ\mu_2<\delta or μn<n\mu_n<n; by Lemma 2.1, the latter holds exactly when GG is connected. The identities μ2=δ\mu_2=\delta and μn=n\mu_n=n are necessary for equality but not sufficient: the graph in Example 4.4 satisfies both identities, and (4) is strict for it. The complete component in Theorem 1.1(iii) is therefore an essential part of the characterization.

Example 4.4. Let G=P3‾⊔P3‾G=\overline{P_3}\sqcup\overline{P_3}, where P3P_3 is the path on three vertices. Since L(P3)L(P_3) has eigenvalues 0,1,30,1,3, Lemma 2.1 gives μ2(G)=6−3=3\mu_2(G)=6-3=3 and μ6(G)=6\mu_6(G)=6. Moreover, δ(G)=3\delta(G)=3, so the right-hand side of (4) equals 11. We show that t(G)=3/2t(G)=3/2.

The graph GG is the join (K2⊔K1)∨(K2⊔K1)(K_2\sqcup K_1)\vee(K_2\sqcup K_1). If G−SG-S contains a vertex from each join factor, then G−SG-S is connected, since these two vertices are adjacent and every other vertex of G−SG-S is adjacent to one of them. Hence every vertex cut contains one of the two factors and has at least three vertices. Moreover, choosing one vertex from each component of G−SG-S gives an independent set, so c(G−S)≤α(G)=2c(G-S)\leq\alpha(G)=2. Thus every vertex cut has ratio at least 3/23/2, and deleting either join factor attains this value. Accordingly, G‾=P3‾⊔P3‾\overline{G}=\overline{P_3}\sqcup\overline{P_3} has no complete component of order at least two, and condition (iii) of Theorem 1.1 fails.

Regular graphs and toughness cuts

We now derive Corollary 1.2 and determine all toughness cuts of an equality graph. Under regularity, every component of the complement is a copy of KmK_m; in general, the components of the complement isomorphic to KmK_m correspond exactly to the toughness cuts.

Proof of Corollary 1.2. Let GG be a regular equality graph of order nn. By Theorem 1.1, there is an integer m≥2m\geq2 such that δ(G)=n−m\delta(G)=n-m and ρL(G‾)=n−μ2(G)=m\rho_L(\overline{G})=n-\mu_2(G)=m. Since GG is regular of degree n−mn-m, its complement is (m−1)(m-1)-regular. Let CC be a connected component of G‾\overline{G}. If CC were noncomplete, Lemma 2.3 applied to CC would give

ρL(C)>δ(C)+1=m,\rho_L(C)>\delta(C)+1=m,

contrary to ρL(G‾)=m\rho_L(\overline{G})=m. Hence every component of G‾\overline{G} is complete and (m−1)(m-1)-regular, that is, isomorphic to KmK_m. Since GG is connected, G‾\overline{G} has at least two components.

Conversely, if G‾\overline{G} is the disjoint union of r≥2r\geq2 copies of KmK_m with m≥2m\geq2, then G‾\overline{G} satisfies Theorem 1.1(iii), so G=Km,…,mG=K_{m,\ldots,m} is an equality graph. Its order is rmrm, and (5) gives t(G)=(rm−m)/m=r−1t(G)=(rm-m)/m=r-1. □

Theorem 5.1. Let GG be an equality graph of order nn, and put m=α(G)m = \alpha(G). For a subset S⊆V(G)S \subseteq V(G), the following statements are equivalent.

(i) SS is a toughness cut of GG.

(ii) V(G)∖SV(G) \setminus S is a maximum independent set of GG.

(iii) V(G)∖SV(G) \setminus S is the vertex set of a component of GG isomorphic to KmK_m.

Consequently, the number of toughness cuts of GG equals the number of components of G‾\overline{G} isomorphic to KmK_m. Every toughness cut has size n−m=δ(G)n-m=\delta(G) and leaves exactly mm components.

Proof. The implication (i)⇒\Rightarrow(ii) is part of Lemma 4.1.

For (ii)⇒\Rightarrow(iii), let U=V(G)∖SU=V(G)\setminus S be a maximum independent set, so that ∣U∣=m|U|=m. By Theorem 1.1, δ(G)=n−m\delta(G)=n-m. Every vertex of UU has all its neighbors in SS and at least n−m=∣S∣n-m=|S| of them, so it is adjacent to every vertex of SS. In G‾\overline{G}, the set UU therefore induces KmK_m and sends no edges to SS; hence it is the vertex set of a component.

For (iii)⇒\Rightarrow(i), the graph G−SG-S consists of m≥2m\ge2 isolated vertices, and ∣S∣=n−m|S|=n-m. Its ratio is (n−m)/m=t(G)(n-m)/m=t(G) by (5), so SS is a toughness cut.

Distinct components of G‾\overline{G} have distinct complements in V(G)V(G), which gives the counting statement. The remaining assertions follow from (iii) and (5). □

In particular, the maximum independent sets of an equality graph are pairwise disjoint, there are at most ⌊n/m⌋\lfloor n/m\rfloor of them, and the toughness cut is unique if and only if G‾\overline{G} has exactly one component isomorphic to KmK_m.

Corollary 5.2. Every equality graph GG satisfies κ(G)=δ(G)=μ2(G)\kappa(G)=\delta(G)=\mu_2(G), and every toughness cut of GG is a minimum vertex cut.

Proof. By Lemma 2.3 and Theorem 1.1, every vertex cut has size at least μ2(G)=δ(G)\mu_2(G)=\delta(G). By Theorem 5.1, every toughness cut has size δ(G)\delta(G). □

Example 5.3. A minimum vertex cut of an equality graph need not be a toughness cut. Let G=K3∨(K2⊔K1)G=K_3\vee(K_2\sqcup K_1). Its complement is K3⊔P3K_3\sqcup P_3, and ρL(P3)=3\rho_L(P_3)=3, so Theorem 1.1 applies with m=3m=3 and gives δ(G)=3\delta(G)=3 and t(G)=1t(G)=1. Deleting the three vertices of K2⊔K1K_2\sqcup K_1 leaves three isolated vertices; this is a toughness cut. Deleting instead the three vertices of K3K_3 leaves K2⊔K1K_2\sqcup K_1, which has two components. This minimum vertex cut has ratio 3/23/2.

Examples and recognition

The join description

By Theorem 1.1, applied with H=F‾H=\overline{F}, a connected noncomplete graph GG is an equality graph if and only if

G≅Km‾∨H,m≥2,∣V(H)∣≥1,ρL(H‾)≤m.(39)G \cong\overline{K_m}\vee H,\qquad m\ge2,\qquad|V(H)|\ge1,\qquad\rho_L(\overline{H})\le m. \tag*{(39)}

In this case, m=α(G)m=\alpha(G) and ∣V(H)∣=δ(G)|V(H)|=\delta(G). If HH has order s≥2s\ge2, then Lemma 2.1 rewrites the condition on HH as

μ2(H)≥s−m;(40)\mu_2(H)\ge s-m; \tag*{(40)}

this includes disconnected graphs HH, for which μ2(H)=0\mu_2(H)=0. If s=1s=1, the condition in (39) holds trivially. With s=δs=\delta and m=n−δm=n-\delta, condition (40) is the form in which Huang, Das, and Zhu [13] describe their equality family.

The condition ρL(H‾)≤m\rho_L(\overline{H})\le m holds automatically when ∣V(H)∣≤m|V(H)|\le m, because the Laplacian spectral radius of a graph is at most its order (Lemma 2.1). Hence every graph on at most mm vertices occurs as HH. Adding edges to HH also preserves equality.

Proposition 6.1. Let G=K‾m∨HG = \overline{K}_m \vee H satisfy (39), and let H′H' be obtained from HH by adding edges on the same vertex set. Then K‾m∨H′\overline{K}_m \vee H' is an equality graph with the same toughness and independence number as GG.

Proof. The graph H′‾\overline{H'} is obtained from H‾\overline{H} by deleting edges. Deleting an edge uvuv subtracts the positive semidefinite matrix (eu−ev)(eu−ev)T(\mathbf{e}_u-\mathbf{e}_v)(\mathbf{e}_u-\mathbf{e}_v)^{\mathsf{T}} from the Laplacian matrix, so the maximum Rayleigh quotient gives ρL(H′‾)≤ρL(H‾)≤m\rho_L(\overline{H'}) \le\rho_L(\overline{H}) \le m. By Theorem 1.1, both graphs are equality graphs with independence number mm and toughness ∣V(H)∣/m|V(H)|/m.

Example 6.2. Let G=Kn1,…,nrG = K_{n_1,\ldots,n_r} with r≥2r \ge2 and m=max⁡ini≥2m = \max_i n_i \ge2. Its complement is Kn1∪˙⋯∪˙KnrK_{n_1} \mathbin{\dot\cup} \cdots\mathbin{\dot\cup} K_{n_r}. Removing one component isomorphic to KmK_m leaves a disjoint union of complete graphs of order at most mm, whose Laplacian spectral radius is at most mm. Hence GG is an equality graph with t(G)=(n−m)/mt(G) = (n-m)/m. By Theorem 5.1, its toughness cuts are exactly the complements of its parts of size mm.

Example 6.3. For m≥2m \ge2 and s≥1s \ge1, the graph K‾m∨K‾s\overline{K}_m \vee\overline{K}_s is an equality graph with toughness s/ms/m, since its complement is Km∪˙KsK_m \mathbin{\dot\cup} K_s and ρL(Ks)=0\rho_L(K_s) = 0. In particular, every positive rational number is the toughness of an equality graph: for positive integers aa and bb, the graph K‾2b∨K‾2a\overline{K}_{2b} \vee\overline{K}_{2a} has toughness a/ba/b.

In (39), the factor K‾m\overline{K}_m is a maximum independent set of GG. For example, K2,3=K‾3∨K‾2K_{2,3} = \overline{K}_3 \vee\overline{K}_2 satisfies (39) with m=3m = 3, because ρL(K‾2)=2≤3\rho_L(\overline{K}_2) = 2 \le3; the decomposition K2,3=K‾2∨K‾3K_{2,3} = \overline{K}_2 \vee\overline{K}_3 does not, because ρL(K‾3)=3>2\rho_L(\overline{K}_3) = 3 > 2.

Noncomplete components of the complement

The following equality graphs are not regular, and their complements have noncomplete components of order larger than the independence number. For q≥1q \ge1, let PqP_q be the path on qq vertices, and for q≥3q \ge3, let CqC_q be the cycle on qq vertices.

Example 6.4. The graph G=K‾4∪˙C5G = \overline{K}_4 \mathbin{\dot\cup} C_5 is an equality graph. Indeed, the characteristic polynomial of L(C5)L(C_5) is x(x2−5x+5)2x(x^2 - 5x + 5)^2, so

ρL(C5)=5+52<4.\rho_L(C_5) = \frac{5+\sqrt{5}}{2} < 4.

Theorem 1.1 gives n=9n = 9, μ2=δ=5\mu_2 = \delta= 5, μn=9\mu_n = 9, and t(G)=5/4t(G) = 5/4. The four vertices corresponding to K‾4\overline{K}_4 have degree five in GG, and the other five vertices have degree six. Thus GG is not regular, and the component C5C_5 of G‾\overline{G} has order larger than α(G)=4\alpha(G) = 4.

Example 6.5. For every q≥1q \ge1, the graph Gq=K‾4∪˙PqG_q = \overline{K}_4 \mathbin{\dot\cup} P_q is an equality graph with t(Gq)=q/4t(G_q) = q/4 and α(Gq)=4\alpha(G_q) = 4. For q=1q = 1, the graph P1P_1 has Laplacian spectral radius zero; for q≥2q \ge2, Lemma 2.2 gives ρL(Pq)≤4\rho_L(P_q) \le4. The same holds with PqP_q replaced by any nonempty disjoint union of paths and cycles. Hence the orders of the noncomplete components of the complement of an equality graph are not bounded in terms of its independence number.

For independence number two or three, the condition in Theorem 1.1(iii) reduces to a finite list of admissible components.

Proposition 6.6. Let GG be a connected noncomplete graph.

(i) GG is an equality graph with α(G)=2\alpha(G) = 2 if and only if every component of G‾\overline{G} is K1K_1 or K2K_2 and at least one component is K2K_2. ::

(ii) GG is an equality graph with α(G)=3\alpha(G)=3 if and only if every component of G‾\overline{G} is one of K1K_1, K2K_2, P3P_3, K3K_3 and at least one component is K3K_3.

Proof. (i) By Theorem 1.1, GG is an equality graph with α(G)=2\alpha(G)=2 if and only if G‾\overline{G} has a component K2K_2 and the remaining components have Laplacian spectral radius at most two. By Lemma 2.2, a graph with Laplacian spectral radius at most two has maximum degree at most one, so its components are K1K_1 and K2K_2. Conversely, ρL(K1)=0\rho_L(K_1)=0 and ρL(K2)=2\rho_L(K_2)=2.

(ii) Similarly, GG is an equality graph with α(G)=3\alpha(G)=3 if and only if G‾\overline{G} has a component K3K_3 and the remaining components have Laplacian spectral radius at most three. By Lemma 2.2, such components have maximum degree at most two, so each is a path or a cycle. None of them contains P4P_4 as a subgraph: the vector (1,−2,2,−1)T(1,-2,2,-1)^{\mathrm{T}} on the consecutive vertices of P4P_4, extended by zeros, has Rayleigh quotient at least 34/10>334/10>3 in any graph containing this path, because additional edges contribute nonnegative terms to (2.1). Hence the admissible components are exactly K1K_1, K2K_2, P3P_3, and K3K_3. Each of them has at most three vertices, so its Laplacian spectral radius is at most three by Lemma 2.1, with ρL(K1)=0\rho_L(K_1)=0.

A recognition criterion

By (5), the parameter mm in Theorem 1.1 is determined by the minimum degree. This gives a test for equality that requires neither the independence number nor a toughness cut.

Proposition 6.7. Let GG be a connected noncomplete graph of order nn, and put m=n−δ(G)m=n-\delta(G). Then GG is an equality graph if and only if G‾\overline{G} has a component C≅KmC\cong K_m such that the matrix mI−L(F)mI-L(F) is positive semidefinite, where F=G‾−V(C)F=\overline{G}-V(C). In this case, the toughness cuts of GG are exactly the complements of the components of GG isomorphic to KmK_m.

Proof. By (5), every integer mm satisfying Theorem 1.1 (iii) equals n−δ(G)n-\delta(G). Hence GG is an equality graph if and only if G‾\overline{G} has a component C≅KmC\cong K_m with m=n−δ(G)m=n-\delta(G) such that F=G‾−V(C)F=\overline{G}-V(C) satisfies ρL(F)≤m\rho_L(F)\le m; the graph FF has at least one vertex because GG is connected. Since L(F)L(F) is symmetric, ρL(F)≤m\rho_L(F)\le m if and only if mI−L(F)mI-L(F) is positive semidefinite. The statement about toughness cuts is Theorem 5.1.

References

References

  1. [1]N. Alon, Tough Ramsey graphs without short cycles, J. Algebraic Combin. 4 (1995), no. 3, 189–195.DOI
  2. [2]D. Bauer, H. Broersma, and E. Schmeichel, Toughness in graphs—a survey, Graphs Combin. 22 (2006), no. 1, 1–35.DOI
  3. [3]A. E. Brouwer, Toughness and spectrum of a graph, Linear Algebra Appl. 226–228 (1995), 267–271.DOI
  4. [4]A. E. Brouwer and W. H. Haemers, Spectra of graphs, Universiteit, Springer, New York, 2012.
  5. [5]V. Chvátal, Tough graphs and Hamiltonian circuits, Discrete Math. 5 (1973), 215–228.
  6. [6]S. M. Cioabă and X. Gu, Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs, Czechoslovak Math. J. 66(141) (2016), no. 3, 913–924.
  7. [7]S. M. Cioabă and W. Wong, The spectrum and toughness of regular graphs, Discrete Appl. Math. 176 (2014), 43–52.arxiv.org/abs/1312.2247
  8. [8]M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Math. J. 23(98) (1973), no. 2, 298–305.DOI
  9. [9]G. Greaves and H. Zhu, A proof of Haemers’ toughness conjecture, preprint (2026), arXiv:2605.15738.arxiv.org/abs/2605.15738
  10. [10]X. Gu, A proof of Brouwer’s toughness conjecture, SIAM J. Discrete Math. 35 (2021), no. 2, 948–952.DOI
  11. [11]X. Gu and W. H. Haemers, Graph toughness from Laplacian eigenvalues, Algebraic Combin. 5 (2022), no. 1, 53–61.arxiv.org/abs/2104.03845
  12. [12]W. H. Haemers, Toughness conjecture, ResearchGate (2020). Available at https://www.researchgate.net/publication/348437253 (last accessed 13 Nov 2026).
  13. [13]X. Huang, K. C. Das, and S. Zhu, Toughness and normalized Laplacian eigenvalues of graphs, Appl. Math. Comput. 425 (2022), Paper No. 127075.arxiv.org/abs/2301.02981
  14. [14]S. J. Kirkland, J. J. Molitierno, M. Neumann, and B. L. Shader, On graphs with equal algebraic and vertex connectivity, Linear Algebra Appl. 341 (2002), nos. 1–3, 45–56.DOI

Paper details

vlnc:W_e9jtz2fh
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents