WorksMathematics
Graphs attaining Haemers' toughness bound
Abstract
Haemers \cite{Haemers2020} conjectured that every connected noncomplete graph satisfies , where is the toughness of , and 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 and a subset , let denote the subgraph induced by . For , write , and let be the number of connected components of . A set is a vertex cut if , and the vertex connectivity of a noncomplete graph is the minimum cardinality among all vertex cuts of . The toughness of a connected noncomplete graph is
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 is a Hamiltonian cycle of and is a nonempty vertex set, then is a spanning subgraph of with at most components. Hence every Hamiltonian graph is -tough, that is, . 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 -regular graph , let be the largest absolute value of an adjacency eigenvalue other than . Brouwer proved that and conjectured that ; 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 provides a natural framework for spectral analysis, where is the adjacency matrix of and is the diagonal matrix of its vertex degrees. For a graph of order , the Laplacian eigenvalues of are denoted by
and we omit the argument when the graph is clear from the context. The eigenvalue is the algebraic connectivity introduced by Fiedler [8], and denotes the minimum degree. Gu and Haemers [11] proved that every connected noncomplete graph of order satisfies
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
Since and (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 denote the complement of , the complete graph on vertices, and the disjoint union of and . The join is defined as the disjoint union together with all edges joining and . The Laplacian spectral radius of a nonempty graph is the largest eigenvalue of , thus if and only if has no edges. Finally, denotes the independence number of , the maximum size of a set of pairwise nonadjacent vertices.
Theorem 1.1. Let be a connected noncomplete graph of order with minimum degree and Laplacian eigenvalues . The following statements are equivalent.
(i) .
(ii) .
(iii) There exist an integer and a graph with at least one vertex such that and .
If these statements hold, then the integer in (iii) equals , and
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
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 with : the graph contains an independent set of size whose vertices are adjacent to all other vertices, and the remaining part is constrained only through the Laplacian spectral radius of its complement. In particular, the components of need not be complete, and their orders are not bounded in terms of (Examples 6.4 and 6.5).
Regularity removes this freedom. For positive integers , the complete multipartite graph has independent parts of sizes 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, with parts for some . Its toughness is then .
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 isomorphic to (Theorem 5.1). Consequently, every equality graph satisfies , and each of its toughness cuts is a minimum vertex cut (Corollary 5.2). Fiedler [8] proved that 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 and , 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 , let be the components of , and let be the average number of neighbors in of a vertex of . Compressing onto the span of the characteristic vectors of and yields two inequalities. The first, which uses , gives (Lemma 3.1). The second, which uses , shows that at most one is smaller than (Lemma 3.2). The key step is Proposition 3.3: if some is smaller than , then the ratio is strictly larger than . Therefore a cut attaining equality has for every , and the equality cases of Lemma 3.1 force every to be a single vertex of degree (Proposition 3.4).
Now let be a toughness cut of an equality graph. The vertices outside form an independent set, and each of them has degree . A Rayleigh quotient argument shows that they have a common neighborhood (Lemma 2.4), and the minimality of forces this neighborhood to be all of (Lemma 4.1). This gives the decomposition of 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 of a graph , we write for its degree, for its neighborhood, and for its closed neighborhood. For disjoint vertex sets and , let be the number of edges with one end in and the other in . The maximum degree of is . We omit the subscript when the graph is clear from the context.
Vectors are real column vectors indexed by the vertices of the graph under consideration. We write for the all-ones vector, for the all-ones matrix, for the coordinate vector of a vertex , and for the characteristic vector of a vertex set . The identity matrix is , with its order determined by the context. For every vector ,
Hence is positive semidefinite, and its kernel consists of the vectors that are constant on each connected component of . For a graph of order ,
Expanding in an orthonormal eigenbasis of shows that every nonzero vector attaining the minimum in (2.2) is a -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 be a graph of order . Then
Moreover, , with equality if and only if is disconnected.
Proof. The matrix identity follows by comparing diagonal and off-diagonal entries. Both Laplacian matrices annihilate , and on their sum acts as . Hence the eigenvalues of on are for , and the largest of them is . The remaining eigenvalue of , on , is zero, so .
Since is positive semidefinite, every eigenvalue of on is at most , and equality occurs if and only if has a nonzero null vector orthogonal to . By (2.1), this happens if and only if has at least two connected components. □
Lemma 2.2. Let be a graph with at least one edge. Then
More generally, for every vertex of positive degree, and this inequality is strict if some edge joins to .
Proof. Fix a vertex of positive degree . Define by , for , and for all other vertices . Then , and (2.1) gives
@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 of a graph , we write for its degree, for its neighborhood, and for its closed neighborhood. For disjoint vertex sets and , let be the number of edges with one end in and the other in . The maximum degree of is . We omit the subscript when the graph is clear from the context.
Vectors are real column vectors indexed by the vertices of the graph under consideration. We write for the all-ones vector, for the all-ones matrix, for the coordinate vector of a vertex , and for the characteristic vector of a vertex set . The identity matrix is , with its order determined by the context. For every vector ,
Hence is positive semidefinite, and its kernel consists of the vectors that are constant on each connected component of . For a graph of order ,
Expanding in an orthonormal eigenbasis of shows that every nonzero vector attaining the minimum in (2.2) is a -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 be a graph of order . Then
Moreover, , with equality if and only if is disconnected.
Proof. The matrix identity follows by comparing diagonal and off-diagonal entries. Both Laplacian matrices annihilate , and on their sum acts as . Hence the eigenvalues of on are for , and the largest of them is . The remaining eigenvalue of , on , is zero, so .
Since is positive semidefinite, every eigenvalue of on is at most , and equality occurs if and only if has a nonzero null vector orthogonal to . By (2.1), this happens if and only if has at least two connected components. □
Lemma 2.2. Let be a graph with at least one edge. Then
More generally, for every vertex of positive degree, and this inequality is strict if some edge joins to .
Proof. Fix a vertex of positive degree . Define by , for , and for all other vertices . Then , and (2.1) gives
@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 of a graph , we write for its degree, for its neighborhood, and for its closed neighborhood. For disjoint vertex sets and , let be the number of edges with one end in and the other in . The maximum degree of is . We omit the subscript when the graph is clear from the context.
Vectors are real column vectors indexed by the vertices of the graph under consideration. We write for the all-ones vector, for the all-ones matrix, for the coordinate vector of a vertex , and for the characteristic vector of a vertex set . The identity matrix is , with its order determined by the context. For every vector ,
Hence is positive semidefinite, and its kernel consists of the vectors that are constant on each connected component of . For a graph of order ,
Expanding in an orthonormal eigenbasis of shows that every nonzero vector attaining the minimum in (2.2) is a -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 be a graph of order . Then
Moreover, , with equality if and only if is disconnected.
Proof. The matrix identity follows by comparing diagonal and off-diagonal entries. Both Laplacian matrices annihilate , and on their sum acts as . Hence the eigenvalues of on are for , and the largest of them is . The remaining eigenvalue of , on , is zero, so .
Since is positive semidefinite, every eigenvalue of on is at most , and equality occurs if and only if has a nonzero null vector orthogonal to . By (2.1), this happens if and only if has at least two connected components. □
Lemma 2.2. Let be a graph with at least one edge. Then
More generally, for every vertex of positive degree, and this inequality is strict if some edge joins to .
Proof. Fix a vertex of positive degree . Define by , for , and for all other vertices . Then , and (2.1) gives
@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 of a graph , we write for its degree, for its neighborhood, and for its closed neighborhood. For disjoint vertex sets and , let be the number of edges with one end in and the other in . The maximum degree of is . We omit the subscript when the graph is clear from the context.
Vectors are real column vectors indexed by the vertices of the graph under consideration. We write for the all-ones vector, for the all-ones matrix, for the coordinate vector of a vertex , and for the characteristic vector of a vertex set . The identity matrix is , with its order determined by the context. For every vector ,
Hence is positive semidefinite, and its kernel consists of the vectors that are constant on each connected component of . For a graph of order ,
Expanding in an orthonormal eigenbasis of shows that every nonzero vector attaining the minimum in (2.2) is a -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 be a graph of order . Then
Moreover, , with equality if and only if is disconnected.
Proof. The matrix identity follows by comparing diagonal and off-diagonal entries. Both Laplacian matrices annihilate , and on their sum acts as . Hence the eigenvalues of on are for , and the largest of them is . The remaining eigenvalue of , on , is zero, so .
Since is positive semidefinite, every eigenvalue of on is at most , and equality occurs if and only if has a nonzero null vector orthogonal to . By (2.1), this happens if and only if has at least two connected components. □
Lemma 2.2. Let be a graph with at least one edge. Then
More generally, for every vertex of positive degree, and this inequality is strict if some edge joins to .
Proof. Fix a vertex of positive degree . Define by , for , and for all other vertices . Then , and (2.1) gives
The lower bounds and the strictness assertion follow from the maximum Rayleigh quotient; for the first inequality in (2.4), choose of maximum degree. For the upper bound, (2.1) gives, for every ,
Taking the maximum Rayleigh quotient completes the proof. □
Lemma 2.3. Let be a connected noncomplete graph of order with minimum degree . Then
Moreover, for every vertex cut of ; that is, .
Proof. Since is connected, the kernel of is spanned by , and therefore .
Let be a vertex cut, and let and be the vertex sets of two distinct components of . Define to be on , on , and elsewhere. Then and . By (2.1), only edges between and contribute to , and every vertex of has at most neighbors in . Hence , and (2.2) gives .
Let be a vertex of degree . Since is noncomplete, . Deleting therefore isolates and leaves at least one further vertex, so is a vertex cut and . Since is connected and is nonempty, some edge joins to , and Lemma 2.2 gives . Finally, by Lemma 2.1. □
Lemma 2.4. Let be a connected graph, and let and be distinct nonadjacent vertices with . Then .
Proof. The vector is orthogonal to . Since and are not adjacent,
Thus attains the minimum in (2.2), and . At a vertex , this equation reads . Hence every such is adjacent to if and only if it is adjacent to . □
Vertex cuts and the equality case
Throughout this section, is a connected noncomplete graph of order with minimum degree and Laplacian eigenvalues . Fix a vertex cut , let be the components of , where , and set
Thus is the average number of neighbors in of a vertex of . Since is connected, . A vertex of has at most neighbors outside , so
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 forces strict inequality.
Let be the matrix whose th column is for and whose last column is . These columns are orthonormal, and a direct computation shows that the compression is
The matrices and are positive semidefinite; the second vanishes on and agrees with on . Hence their compressions by are positive semidefinite as well.
Lemma 3.1. In the notation of (25), for every , and
Moreover, for every ,
where the second inequality is strict if and only if . Consequently,
Proof. The matrix , which is the compression of by , is positive semidefinite. For , its th diagonal entry is , and its entry is nonzero. In a positive semidefinite matrix, a zero diagonal entry forces the corresponding row to vanish, as the principal submatrices show. Hence .
The leading principal submatrix of is therefore diagonal and positive definite, and its Schur complement in is nonnegative:
This proves (28).
The first inequality in (29) is (26). For the second,
which is nonnegative, and positive if and only if , because by Lemma 2.3. Finally, (29) gives for every , and substituting these inequalities into (28) yields (30). □
Lemma 3.2. In the notation of (25), any two distinct indices and satisfy
In particular, at most one of is smaller than . If , then for every , and
Proof. The leading principal submatrix of the compression of is
and it is positive semidefinite. For distinct and , evaluate its quadratic form at the vector with th coordinate , th coordinate , and all other coordinates zero. This vector is orthogonal to , so the rank-one term vanishes, and (31) follows. The assertions about the signs of follow immediately.
Now suppose that . Then every diagonal entry is nonzero, and exactly one of them is negative. By the determinant formula for a rank-one perturbation of a diagonal matrix,
Since and the product is negative, the factor in parentheses is nonpositive. Separating the term and multiplying by gives (32). □
Proposition 3.3. In the notation of (25), if for some , then
Proof. Renumber the components so that , and put
By Lemma 3.2, for every . Suppose, for a contradiction, that . Combined with (30), this gives , that is,
In particular, for every .
Substitute into (32) and multiply by . Since and , we obtain
On the other hand, multiplying (28) by gives
Insert (35) and subtract from both sides. Since , this yields
Using , we rewrite each factor in parentheses as
Since by Lemma 2.3, dividing (36) by gives
By (29), . Together with , , and , this gives
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 of satisfies
If equality holds, then every component of is a single vertex of degree , and .
Proof. If for some , then Proposition 3.3 gives strict inequality in (37). Otherwise for every , and (30) gives . This proves (37).
Suppose that equality holds. Then for every by Proposition 3.3, and (28) and (29) give
Hence all these inequalities are equalities. The last one gives for every . Since , the middle one gives , so both inequalities in (29) are equalities. By Lemma 3.1, this forces , and hence , because . For a singleton component, is the degree of its vertex. Hence every component of is a single vertex of degree , and .
Taking the minimum of (37) over all vertex cuts recovers (4). Moreover, Proposition 3.4 reduces the equality problem to vertex cuts such that is an independent set of vertices of degree .
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 be an equality graph of order , and let be a toughness cut of . Then is a maximum independent set, every vertex of is adjacent to every vertex of , and
Proof. Put and . Since is a toughness cut, . By Proposition 3.4, every component of is a single vertex of degree , and . Thus is an independent set of vertices of degree , , and . By Lemma 2.4, the vertices of have a common neighborhood , and .
Suppose that is nonempty. Deleting isolates the vertices of , and the vertices of form at least one further component. Hence
a contradiction. Therefore . Thus every vertex of is adjacent to every vertex of , , and .
The equality now reads . Since , we obtain . Finally, (6) gives , so the independent set is maximum. □
Proof of Theorem 1.1. (i) implies (ii) and (iii). Assume (i), let be a toughness cut, and put and . By Lemma 4.1, is a maximum independent set of size , and every vertex of is adjacent to every vertex of . Hence is a component of , and
where has vertices. By Lemma 2.1 and , we have . Since is block diagonal with blocks and , it follows that , which proves (iii). Moreover, , which proves (ii).
(iii) implies (i). Assume (iii). Since and , we have . As is disconnected, Lemma 2.1 gives
The vertices corresponding to have degree in , so , and hence . Deleting the other vertices leaves isolated vertices, so
The reverse inequality is Proposition 3.4. This proves (i) and (5). Finally, by (6), and the vertices corresponding to form an independent set in ; hence .
(ii) implies (iii). Assume (ii). By (6), . Let be a maximum independent set, and put . Every vertex of has all its neighbors outside , so its degree is at most . Hence it has degree exactly and is adjacent to every vertex outside . Therefore
Here because is noncomplete, and has at least one vertex because is connected. As before, Lemma 2.1 gives , and hence . 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 of order , the following three equalities are equivalent:
In particular, the bounds (2), (3), and (4) have the same equality graphs, namely those described in Theorem 1.1.
Hence each of the last two equalities implies the first. Conversely, the first equality gives and by Theorem 1.1, and then the three ratios coincide. □
Remark 4.3. By Theorem 1.1, inequality (4) is strict whenever or ; by Lemma 2.1, the latter holds exactly when is connected. The identities and 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 , where is the path on three vertices. Since has eigenvalues , Lemma 2.1 gives and . Moreover, , so the right-hand side of (4) equals . We show that .
The graph is the join . If contains a vertex from each join factor, then is connected, since these two vertices are adjacent and every other vertex of 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 gives an independent set, so . Thus every vertex cut has ratio at least , and deleting either join factor attains this value. Accordingly, 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 ; in general, the components of the complement isomorphic to correspond exactly to the toughness cuts.
Proof of Corollary 1.2. Let be a regular equality graph of order . By Theorem 1.1, there is an integer such that and . Since is regular of degree , its complement is -regular. Let be a connected component of . If were noncomplete, Lemma 2.3 applied to would give
contrary to . Hence every component of is complete and -regular, that is, isomorphic to . Since is connected, has at least two components.
Conversely, if is the disjoint union of copies of with , then satisfies Theorem 1.1(iii), so is an equality graph. Its order is , and (5) gives . □
Theorem 5.1. Let be an equality graph of order , and put . For a subset , the following statements are equivalent.
(i) is a toughness cut of .
(ii) is a maximum independent set of .
(iii) is the vertex set of a component of isomorphic to .
Consequently, the number of toughness cuts of equals the number of components of isomorphic to . Every toughness cut has size and leaves exactly components.
Proof. The implication (i)(ii) is part of Lemma 4.1.
For (ii)(iii), let be a maximum independent set, so that . By Theorem 1.1, . Every vertex of has all its neighbors in and at least of them, so it is adjacent to every vertex of . In , the set therefore induces and sends no edges to ; hence it is the vertex set of a component.
For (iii)(i), the graph consists of isolated vertices, and . Its ratio is by (5), so is a toughness cut.
Distinct components of have distinct complements in , 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 of them, and the toughness cut is unique if and only if has exactly one component isomorphic to .
Corollary 5.2. Every equality graph satisfies , and every toughness cut of is a minimum vertex cut.
Proof. By Lemma 2.3 and Theorem 1.1, every vertex cut has size at least . By Theorem 5.1, every toughness cut has size . □
Example 5.3. A minimum vertex cut of an equality graph need not be a toughness cut. Let . Its complement is , and , so Theorem 1.1 applies with and gives and . Deleting the three vertices of leaves three isolated vertices; this is a toughness cut. Deleting instead the three vertices of leaves , which has two components. This minimum vertex cut has ratio .
Examples and recognition
The join description
By Theorem 1.1, applied with , a connected noncomplete graph is an equality graph if and only if
In this case, and . If has order , then Lemma 2.1 rewrites the condition on as
this includes disconnected graphs , for which . If , the condition in (39) holds trivially. With and , condition (40) is the form in which Huang, Das, and Zhu [13] describe their equality family.
The condition holds automatically when , because the Laplacian spectral radius of a graph is at most its order (Lemma 2.1). Hence every graph on at most vertices occurs as . Adding edges to also preserves equality.
Proposition 6.1. Let satisfy (39), and let be obtained from by adding edges on the same vertex set. Then is an equality graph with the same toughness and independence number as .
Proof. The graph is obtained from by deleting edges. Deleting an edge subtracts the positive semidefinite matrix from the Laplacian matrix, so the maximum Rayleigh quotient gives . By Theorem 1.1, both graphs are equality graphs with independence number and toughness .
Example 6.2. Let with and . Its complement is . Removing one component isomorphic to leaves a disjoint union of complete graphs of order at most , whose Laplacian spectral radius is at most . Hence is an equality graph with . By Theorem 5.1, its toughness cuts are exactly the complements of its parts of size .
Example 6.3. For and , the graph is an equality graph with toughness , since its complement is and . In particular, every positive rational number is the toughness of an equality graph: for positive integers and , the graph has toughness .
In (39), the factor is a maximum independent set of . For example, satisfies (39) with , because ; the decomposition does not, because .
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 , let be the path on vertices, and for , let be the cycle on vertices.
Example 6.4. The graph is an equality graph. Indeed, the characteristic polynomial of is , so
Theorem 1.1 gives , , , and . The four vertices corresponding to have degree five in , and the other five vertices have degree six. Thus is not regular, and the component of has order larger than .
Example 6.5. For every , the graph is an equality graph with and . For , the graph has Laplacian spectral radius zero; for , Lemma 2.2 gives . The same holds with 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 be a connected noncomplete graph.
(i) is an equality graph with if and only if every component of is or and at least one component is . ::
(ii) is an equality graph with if and only if every component of is one of , , , and at least one component is .
Proof. (i) By Theorem 1.1, is an equality graph with if and only if has a component 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 and . Conversely, and .
(ii) Similarly, is an equality graph with if and only if has a component 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 as a subgraph: the vector on the consecutive vertices of , extended by zeros, has Rayleigh quotient at least in any graph containing this path, because additional edges contribute nonnegative terms to (2.1). Hence the admissible components are exactly , , , and . Each of them has at most three vertices, so its Laplacian spectral radius is at most three by Lemma 2.1, with .
A recognition criterion
By (5), the parameter 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 be a connected noncomplete graph of order , and put . Then is an equality graph if and only if has a component such that the matrix is positive semidefinite, where . In this case, the toughness cuts of are exactly the complements of the components of isomorphic to .
Proof. By (5), every integer satisfying Theorem 1.1 (iii) equals . Hence is an equality graph if and only if has a component with such that satisfies ; the graph has at least one vertex because is connected. Since is symmetric, if and only if is positive semidefinite. The statement about toughness cuts is Theorem 5.1.
References
References
- [1]N. Alon, Tough Ramsey graphs without short cycles, J. Algebraic Combin. 4 (1995), no. 3, 189–195.DOI
- [2]D. Bauer, H. Broersma, and E. Schmeichel, Toughness in graphs—a survey, Graphs Combin. 22 (2006), no. 1, 1–35.DOI
- [3]A. E. Brouwer, Toughness and spectrum of a graph, Linear Algebra Appl. 226–228 (1995), 267–271.DOI
- [4]A. E. Brouwer and W. H. Haemers, Spectra of graphs, Universiteit, Springer, New York, 2012.
- [5]V. Chvátal, Tough graphs and Hamiltonian circuits, Discrete Math. 5 (1973), 215–228.
- [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]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]M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Math. J. 23(98) (1973), no. 2, 298–305.DOI
- [9]G. Greaves and H. Zhu, A proof of Haemers’ toughness conjecture, preprint (2026), arXiv:2605.15738.arxiv.org/abs/2605.15738
- [10]X. Gu, A proof of Brouwer’s toughness conjecture, SIAM J. Discrete Math. 35 (2021), no. 2, 948–952.DOI
- [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]W. H. Haemers, Toughness conjecture, ResearchGate (2020). Available at https://www.researchgate.net/publication/348437253 (last accessed 13 Nov 2026).
- [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]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