Let be a graph on vertices. The -token graph (or symmetric -th power) of , denoted by () has as vertices the (︁ )︁ -subsets of vertices from , and two vertices are adjacent when their symmetric diference is a pair of adjacent vertices in . In particular, () is the Johnson graph (, ), which is a distance-regular graph used in coding theory. In this paper, we present some results concerning the (adjacency and Laplacian) spectrum of () in terms of the spectrum of . For instance, when is walk-regular, an exact value for the spectral radius (or maximum eigenvalue) of () is obtained. When is distance-regular, other eigenvalues of its 2-token graph are derived using the theory of equitable partitions. A generalization of Aldous' spectral gap conjecture (which is now a theorem) is proposed.
08
07 87 graph is used. For instance, Rudolph [23] showed that there are cospectral non-isomorphic graphs that can be distinguished by the adjacency spectra of their 2-token graphs, and he also gave an example for the Laplacian spectrum. Audenaert, Godsil, Royle, and Rudolph [1] also proved that 2-token graphs of strongly regular graphs with the same parameters are cospectral and also derived bounds on the (adjacency and Laplacian) eigenvalues of 2() for general graphs. For more information, see again [1] or [12].
What can be said about the spectrum of ()? The three main results that we want to recall are the following.
Rudolph [1]). All the strongly regular graphs with the same parameters have cospectral symmetric squares (or 2-token graphs).
For any graph on vertices, the Laplacian spectrum of its ℎ-token graph is contained in the Laplacian spectrum of its -token graph for every 1 ≤ ℎ ≤ ≤ /2. Theorem 1.3 (Lew [20]). Let have Laplacian eigenvalues 1(= 0) < 2 ≤ · · · ≤ . Let be an eigenvalue of () not in − 1(). Then,
( 2 − + 1) ≤ ≤ .
In this paper, we mainly derive new results about the spectral radius of token graphs, and it is organized as follows. The next section begins with some basic concepts, definitions, and results. More precisely, we recall some known results about the local spectra and derive the basic tools for computing the spectral radius. In Section 3, we introduce the new concepts of -algebraic connectivity and -spectral radius. There, we study some of their properties and propose and conjecture a generalization of Aldou’s spectral gap conjecture, already a theorem (see Caputo, Liggett, and Richthammer [6]). In Section 4, we give both lower and upper bounds for the spectral radius of a token graph, which are shown to be asymptotically tight. In the same section, we present some infinite families in which the exact values of the spectral radius are obtained. Finally, in the last section, we deal with the case of distance-regular and strongly regular graphs, where two results are presented in the form of Audenaert, Godsil, Royle, and Rudolph’s result [1], and Lew’s result [20].
Let be a (simple and connected) graph with vertex set () = {1, 2, . . . , } and edge set (). Let have adjacency matrix , and spectrum , sp ≡ sp = { 00 , 11 , . . . , } where 0 > 1 > · · · > . Thus, by the PerronFrobenius theorem, has spectral radius () = 0.
Let = − be the Laplacian matrix of , with eigenvalues 1(= 0) < 2 ≤ · · · ≤
Recall that 2 is the algebraic connectivity, and is the diagonal matrix whose diagonal entries are the vertex degrees of .
Let have diferent eigenvalues 0 > · · · > , with respective multiplicities 0, . . . , . If is the × matrix whose columns are the orthonormal eigenvectors of , the matrix = ⊤, for = 0, 1, . . . , , is the (principal) idempotent of and represents the orthogonal projection of R onto the eigenspace Ker( − ).
The (-)local multiplicities of the eigenvalue are deifned as
( ) = ‖‖2 = ⟨, ⟩ = () for ∈ and = 0, 1, . . . , , where the vector is an -dimensional vector with a 1 in the -th entry and zeros elsewhere. In particular, ( 0) = 2 > 0, where is the corresponding normalized Perron eigenvector. Al- are, respectively, referred to as the quotient matrix and though the local multiplicities are, of course, not necessar- quotient Laplacian matrix of with respect to . In turn, ily integers, they have nice properties when the graph is these matrices correspond to the quotient (weighted) distudied from a vertex, so justifying their name. Thus, they rected graph / , whose vertices representing the cells, satisfy ∑︀=0 ( ) = 1 and ∑︀∈ ( ) = , for and there is an arc with weight from vertex to ver = 0, 1, . . . , . The number (ℓ) of closed walks of tex if and only if ̸= 0. Of course, if > 0, for length ℓ rooted at vertex can be computed as some = 1, . . . , , the quotient graph (or digraph) / has loops. Given a partition of with cells, let be the characteristic matrix of , that is, the × times (ℓ) = ∑︁ ( ) ℓ (1) matrix whose columns are the characteristic vectors of =0 the cells of . Then, is a regular partition if and only (see Fiol and Garriga [14]). By picking up the eigenvalues if = or = . Moreover, = with non-null local multiplicities, 0(= 0) > 1 > (⊤)− 1⊤, and = (⊤)− 1⊤ . · · · > , we define the (-)local spectrum of as Thus, there is a strong analogy with similar results satisifed by the Laplacian matrices of the ℎ-token graph and ( ) , sp := { 0( 0), 1( 1), . . . , } -token graph of for ℎ ≤ . with (-)local mesh, or set of distinct eigenvalues, ev := { 0 > 1 > · · · > }. The eccentric- 2.4. Walk-regular graphs ity of a vertex satisfies an upper bound similar to that satisfied by the diameter of in terms of its distinct eigenvalues. More precisely, ecc() ≤ = | ev | − 1.
(2) In coding theory, corresponds to the so-called ‘dual degree’ of the trivial code {}. For more information, see Fiol, Garriga, and Yebra [16].
We use the following lemma to prove the results of Section 4. Notice that this is just a reformulation of the power method in terms of the number of walks given by (1).
Lemma 2.1. Let be a finite graph with diferent eigen
> . Let (ℓ) be the number of ℓ-walks values 0 > · · · starting from (any fixed) vertex , and let (ℓ) be the number of closed ℓ-walks rooted at . Then, () = lim ℓ→∞ √ℓ︁(ℓ) = lim sup √ℓ︁(ℓ) ,
ℓ→∞ where ‘ sup’ denotes the supremum.
Let (ℓ) denote the number of closed walks of length ℓ
(ℓ) = (ℓ). If these numbers rooted at vertex , that is, only depend on ℓ, for each ℓ ≥ 0, then is called walkregular, a concept introduced by Godsil and McKay in [18].
Notice that, as (2) = , the degree of vertex , a walk-regular graph is necessarily regular.
Moreover, a graph is called spectrally regular when all vertices have the same local spectrum: sp = sp for any , ∈ . The following result (in Delorme and Tillich [11], Fiol and Garriga [15], and also Godsil and McKay [18]) provide some characterizations of such graphs.
Lemma 2.2 ([11],[15],[18]). Let = (, ) be a graph. The following statements are equivalent.
() is walk-regular. () is spectrally regular. () The spectra of the vertex-deleted subgraphs are all equal: sp ( ∖ ) = sp ( ∖ ) for any , ∈ . () = ⎧ ⎪ ⎨
∑︁ − ⎪ ⎩ =1 −
if ̸= , if = ,
Let = (, ) be a graph with vertex set = (), adjacency matrix , and Laplacian matrix . A partition of its vertex set into cells 1, 2, . . . , is called regular (or equitable) whenever, for any , = 1, . . . , , In this section, we always consider the Laplacian specthe intersection numbers () = |() ∩ |, where trum. Let be a graph on vertices, and () its ∈ , do not depend on the vertex but only on the tok− en(gra)pwhhfeorre,b∈y {co0n,1v,e.n.ie.n,ce},.N0o(te)t h∼=at (()) =∼= cells and . In this case, such numbers are simply 1 (a singleton). Moreover, 1() ∼= . From Dalfó, written as , and the × matrices = (/ ) Duque, Fabila-Monroy, Fiol, Huemer, Trujillo-Negrete, and = (/ ) with entries () = and and Zaragoza Martínez [8], it is known that the Laplacian spectra of the token graphs of satisfy
{0} = sp 0() ⊂ sp 1() ⊂ sp 2() ⊂ · · · ⊂ sp ⌊/2⌋().
(3) Let denote () and () the algebraic connectivity Because of (4), if Conjecture 3.2 holds, also does the (see Fiedler [17]) and the spectral radius of a graph , conjecture proposed in [8], that is, (()) = () respectively. Then, from (3), we have () ≥ (2()) ≥ · · · ≥ () ≤ (2()) ≤ · · · ≤ (⌊/2⌋()), (⌊/2⌋()).
(4) (5) The concepts of algebraic connectivity and spectral radius, together with (3)–(5), suggest the following definitions.
Given a graph on vertices and an integer such that 1 ≤
≤ ⌊ /2⌋, the -algebraic connectivity = () and the -spectral radius = () of are, respectively, the minimum and maximum eigenvalues of the multiset sp () ∖ sp − 1(). the parameters and alwa−y1s exist.
Notice that, since (︀ )︀ > (︀ )︀ for 1 ≤ ≤ ⌊ /2⌋,
For instance, with = 6, the path on 6 vertices, we have (approximately) Moreover, from these definitions, the following facts spectral radius of ).
we have () () ≥ () ≥ 0. () 1() = () (the standard algebraic connectivity of ) and 1() = () (the standard () Since () ∼= (, ) (the Johnson graph), () = () = ( + 1 − ), = 1, . . . , ⌊/2⌋.
In particular, 1() 2() = 2() = 2( − 1), and so on.
= 1() = , ( + 1 = 0, 1, . . . , .
The equalities in () come from the fact that the Johnson graph (, ) has diferent Laplacian eigenvalues = − ), with multiplicities = (︀ )︀ − ︀( − 1 )︀ for
From what is known about token graphs, we can suggest some conjectures and state some results, as follows.
1() ≤ 2() ≤ · · · ≤ ⌊/2⌋().
for any ≤
/2. In fact, the last equality follows from the proof of Aldous’ spectral gap conjecture given by Caputo, Ligget, and Richthammer in [6]. By this result, what we can state is that min{ 2, . . . , ⌊/2⌋} ≥ 1.
1() ≤ 2() ≤ · · · ≤ ⌊/2⌋().
Notice that, from (5), if this conjecture holds, then () = (()) for any ≤ /2.
Lemma 3.4. For any graph and its complementary graph , the -algebraic connectivity and -spectral radius of satisfy
() + () = ( − + 1).
Moreover, () = − (), as it is well known. Corollary 3.5. For any graph on vertices, () ≤ ( − + 1), () ≤ (− + 1), = 1, . . . , ⌊/2⌋. = 1, . . . , ⌊/2⌋.
From Lemma 3.4 and Proposition 5.2, we get the following result, which will be proved in Section 5.
Corollary 3.6. Let be a bipartite distance-regular graph. Let (2/ ) be the quotient matrix in (15) with spectral radius (2/ ). Then, ︃( )︃
2 2() = − (2/ ).
In contrast with the previous section, in this section, we always consider the spectral radius of the adjacency matrix of a (connected) graph. Consider a graph with spectral radius () and vertex-connectivity (the minimum number of vertices whose suppression either disconnects the graph or results in a singleton). By taking the spectral radii of its -deleted subgraphs, with ⊂ | | = < , we define the following two parameters: and () = max{ ( ∖ ) : ⊂ , | | = }, () = min{ ( ∖ ) : ⊂ , | | = }.
Notice that, if is walk-regular, then 1 () 1() = ( ∖ ) for every vertex . If is distanceregular with degree , it is known that it has vertex= connectivity () = (see Brouwer and Koolen [3]). tion of () and () can be drastically reduced by considering only the subsets with diferent ‘distancepattern’ between vertices. For instance, if has diameter Moreover, Dalfó, Van Dam, and Fiol [7] showed that (see again[22, Th. 4]). sp( ∖ ) only depends on the distances in between the vertices of . Thus, for every ≤ − 1, the computa- vertices are = 2 cos () The spectral radius of the -token graph () () = {0, 1, . . . , − 1; 1, 2, . . . , }. (12) (13) , 2 () = 2() = 1m≤ℓa≤x{ ( ∖ {, }) : dist(, ) = ℓ}, 1≤ mℓi≤n{ ( ∖ {, }) : dist(, ) = ℓ}.
In general, by using interlacing (see Haemers [19] or Fiol [13]), we have the following result.
Lemma 4.1. Let be a graph with vertices, vertexThen, for every = 1, . . . , − 1, connectivity , and eigenvalues 1 ≥ 2 ≥ · · · ≥ +1 ≤ () ≤ 1, ≤ () ≤ − . 1 ≤ < , let () and () be the maximum and minimum of the spectral radii of the -deleted subgraphs of , where | | = .
satisfies
− 1() ≤ (()) ≤ − 1(). (8) () If is a graph of order and diameter , the spectral radius of the -token graph () satisfies (()) ≤ () − ︂(
1 ()2 ︂) . (9) () If is walk-regular and = 2 (that is, 2() is the 2-token graph of ), then (2()) = 2 1() = 2 1 ().
(10)
As commented in [22], for large values of () and , the right hand of (9) yields the correct order of magnitude of (), with a proper subgraph of . Thus, we can say that, asymptotically, the spectral radius of () is times the spectral radius of . Moreover, in the case when is regular, () can be rewritten as (2()) ≤ () − ︂(
1 ( + 1) ︂) (11)
Since the diferent eigenvalues of the path on ︁( ︁) +1
for = 1, . . . , , and (,) = √, we get the following results. the spectral radius of the complete bipartite graph is tively, the infinite path and cycle graphs.
Corollary 4.3. Let and be, respectively, the path and cycle graph on vertices. Let ∞ and ∞ be, respec() (2(,)) = 2√︀( − 1).
() (2()) ≤ 4 cos(/ ) and (2(∞)) = 4, () (2()) = 4 cos(/ ) and (2(∞)) = 4, Notice a pair of examples: • 2(3) = 3 = 3 has spectrum {− 1[2], 2},
whereas 2 has {− 1, 1}. • 2(4) √
= 2 2}, whereas 3 has {− 2,4 has spectrum√{− 2√2, 0[6], √2, 0, . .
Thus, in particular ( ) = ( )− 1 and, up to a constant, (x) equals the characteristic polynomial of · · · 12 (2/ ) (for more details, see Cámara, Fàbrega, Fiol,
Let us show an example.
Example 5.3. The Heawood graph (which is the point/line incidence graph of the Fano plane) is a bipartite distance-regular graph with = 14 vertices, diameter three, and intersection array {0, 1, 2; 1, 2, 3} = {3, 2, 2; 1, 1, 3}. The Laplacian spectral radius of is () =
6, and the algebraic connectivity of is 1() = − () = 8. By Proposition 5.2, the 2token graph 2 = 2() has a regular partition with quotient matrix (2/ ) = 2 ⎝ 2 0 ⎞ 3 ⎠ , (2/ ) = 2 ⎝ − 2 ⎛ 2 0 √3. From this and Lemma 3.4, we have that that the conjugate polynomial 3 must satisfy 3(± 3) =
Moreover, in the vein of Lew’s result (see [20]) and, by using interlacing, we get the following consequence.
Corollary 5.5. Let be a distance-regular graph with (adjacency) eigenvalues 0 > 1 > · · · token graph 2() has some eigenvalues 0 > 1 >
> . Then, 2> − 1 satisfying 2 +1 ≤ ≤ 2 ,
= 0, . . . , − 1.
Let be a (connected) strongly regular graph on vertices, which is a distance-regular graph with diameter 2.
Let have parameters (, , , ), that is, is -regular (with 0 = ), 1 = , and 2 = . Then, its intersection matrix is ⎞ ⎠ .
Then, the 2-token graph 2 = 2() has a regular partition with quotient matrix (2/ ) =
2 2 − 2 − 2
2
Royle, and Rudolph in [1], and noted that the adjacency eigenvalues of (2/ ) are 1,2 = + ( − ) ±
√︀[ − ( − )]2 − 4.
They also commented that the positive eigenvalue 1 has a positive eigenvector (Perron vector) and, so, it corresponds to the (adjacency) spectral radius (2()).
In contrast, the quotient Laplacian matrix (2/ ) has eigenvalues 1 = 0 and 2 = 2( − 1) −
2( − ). Now, the eigenvector of 2 is orthogonal to 1. Then, we can only conclude that the Laplacian spectral radius of 2() satisfies (2()) ≥ 2( − 1) − 2( − ).
(16) For instance, the cycle on five vertices 5 is strongly regular with parameters (5, 2, 0, 1). Its Laplacian spectral radius is (approximately) (2()) = 6.2361, whereas the lower bound in (16) gives 4.
1989. 2018. connectivity of a distance-regular graph, European
S. Kirkland, D. Stevanović, Combinatorial Matrix Theory, Advanced Courses in Mathematics - CRM
Barcelona, Birkhüser/Springer, Cham, Switzerland,
Some families of orthogonal polynomials of a discrete variable and their applications to graphs and bations of almost distance-regular graphs, Linear
Such a regular partition was given by Audenaert, Godsil, [10] E. R. van Dam and J. H. Koolen, A new family of
The research of C. Dalfó and M. A. Fiol has been parment under project 2017SGR1087 and by MICINN from 1, 172.
Delorme and
Tillich,
Eigenvalues, eigenspaces and distances to subsets, Discrete Math. 2023.
cally
Rudolph, intuitive
Constructing graph physigrant from the Universitat Politècnica de Catalunya with