Given a graph G, the line graph L(G) of G has the edges of G as its vertices, with two vertices adjacent in L(G) if the corresponding edges have a vertex in common in G. The line graph L(G) can then be decomposed into the Gallai graph Γ(G) and anti-Gallai graph Δ(G), as follows. The Gallai graph Γ(G) of G has the edges of G as its vertices, with two vertices adjacent in Γ(G) if their corresponding edges have a vertex in common in G but do not lie on a common triangle in G. The anti-Gallai graph Δ(G) of G again has the edges of G as its vertices, with two vertices in Δ(G) adjacent if their corresponding edges lie on a common triangle in G. We will refer to G as the underlying graph of the graphs L(G),Γ(G), and Δ(G).

Clearly, L(G) is the edge-disjoint union of Γ(G) and Δ(G). Line graphs have been extensively studied in the literature, however in comparison the theory of Gallai and anti-Gallai graphs has attracted less attention since their introduction in [15]. Good overviews on the topic can be found in [21, 22], while more recent papers include [1, 3, 4, 16, 19, 23, 25, 26]. Furthermore, anti-Gallai graph have found application in linguistics, specifically in identifying polysemous words [2]. This provides motivation for examining the spectral properties of anti-Gallai graphs, particularly in relation to the spectra of their underlying graphs. The spectra of some classes of Gallai and anti-Gallai graphs have already been studied, in [24].

Our interest in this paper is in furthering the study of Gallai and anti-Gallai graphs, particularly in relating spectral and other properties of these graphs with those of their underlying ones. However, there is an issue which presents significant difficulties. Regularity properties of G do not always translate to similar properties of Γ(G) and Δ(G). In particular, G being regular does not imply that Γ(G) and Δ(G) are also regular. Contrast this with the situation for line graphs, where regularity of G implies regularity of L(G), a fact which has greatly facilitated the study of line graphs. However, a key observation in this paper is that Γ(G) and Δ(G) of a strongly regular graph G are regular, and in fact are even edge-regular. This has prompted us to focus on the Gallai and anti-Gallai graphs of strongly regular graphs, and this is the topic of this paper.

We will now define strongly regular graphs. Let G be a k-regular graph with n vertices. The graph G is said to be strongly regular [6] with parameters (n,k,λ,μ) if the following conditions hold:

• (1)

  G is neither complete nor empty;

• (2)

  any two adjacent vertices of G have λ common neighbours;

• (3)

  any two non-adjacent vertices of G have μ common neighbours.

We note that the case μ=0 corresponds to a disjoint union of complete graphs; this is not an interesting case for our purposes, and so we will assume henceforth that μ>0, which implies that G has diameter 2. We note further that the cycles C4 and C5 are strongly regular, however all questions that we will consider reduce to trivialities in these cases, so we will henceforth assume k≥3 whenever G is strongly regular.

A weaker notion is that of an edge-regular graph. An edge-regular graph [7] with parameters (n,k,λ) is a graph on n vertices which is regular of degree k and such that any two adjacent vertices have exactly λ common neighbours. It is evident that strongly regular graphs are edge-regular, but the converse does not hold. In fact, the class of strongly regular graphs is far more restricted than that of edge-regular ones, with a rich structure that has attracted numerous researchers. For excellent overviews on the topic, see [10, 11, 17].

In the next section we give some necessary preliminaries on strongly regular graphs, and the subsequent section concerns the Gallai and anti-Gallai graphs of strongly regular graphs. All graph theoretic notations and terminology not defined here are standard, and can be found for instance in [5, 13].

Henceforth, we assume G is a connected strongly regular graph with parameters (n,k,λ,μ). We will in many cases refer to subgraphs of G, and we must be careful since there are two different types of subgraphs which we will use. The first is an induced subgraph, which is formed from a subset of the vertices of G together with all edges connecting vertices in that set. The more general definition of subgraphs allows for edges from G to be absent even when both endpoints are present in the subgraph. To avoid confusion, we will always refer to induced subgraphs as such, and if we simply consider a subgraph (without the word "induced" present) then it is not assumed to be induced.

The following lemmas contain facts that are certainly known, but the proof is included for the benefit of readers unfamiliar with the structure of strongly regular graphs and standard methods of proof in the field.

Lemma 2.1. Let G be a connected strongly regular graph with parameters (n,k,λ,μ).

• (1)

  μ≥1.

• (2)

  If μ>1 then every pair of non-adjacent vertices must belong to at least one (not necessarily induced) cycle of length 4.

• (3)

  Given an edge e=uv and a vertex w, either there is a vertex y adjacent to all of w,u,v or else w,u,v must belong to a cycle Cn of length at most 5.

• (4)

  Given a pair of edges uv and xy, either there is a vertex z adjacent to all of u,v,x,y, or else both edges lie on a cycle Cn of length at most 6.

• (5)

  If μ=1 then diamonds and C4's are forbidden as induced subgraphs in G (a diamond refers to two triangles sharing a common edge, i.e K4 with an edge removed [23]).

• (6)

  A strongly regular graph is 2-connected (that is, the removal of any vertex does not disconnect the graph).

• (7)

  If λ≤1 then diamonds and K4's are forbidden in G.

Proof. We will employ the following notation, which is not entirely standard in the field. Given vertex x, let Nj(x)={y:d(x,y)=j}. More standard would be to use Γ instead of N, but we will reserve Γ for the Gallai graph. Then, for any x, the vertices of G can be partitioned into the sets {x},N1(x), and N2(x).

Figure 1. The friendship graph F3 and wheel graph W6

(1) This is trivial, since G is connected and of diameter 2.

(2) If y∈N2(x) and μ>1 then there are distinct u,v∈N1(x)∩N1(y) and then xuyv is a cycle of length 4. Note that the triangular graph T(4), which can also be realized as the complement of a perfect matching on 6 vertices, shows that this need not be an induced cycle.

(3) Since G has diameter 2 there are paths of length at most 2 from w to u and from w to v. If these paths do not share vertices other than w then they, together with uv, form a cycle of length at most 5. It is also possible, however, that the paths are of the form wxu and wxv for some vertex x, but then x is adjacent to w,u,v, and the conclusion holds.

(4) Follows similarly, since we can find paths of length at most 2 between u and x and between v and y, and then these paths can then either be used to form a cycle of length at most 6 or else yield a point adjacent to all of u,x,v,y.

(5) These graphs cannot exist as induced subgraphs since both contain vertices of distance 2 from each other but with two paths of length 2 connecting them.

(6) If we remove a vertex w from G, then we must show that the subgraph induced on N1(w)∪N2(w) is connected. Choose x∈N2(w), and let y∈N1(w)∪N2(w). Since the diameter of G is 2, there must be a path of length at most 2 from x to y, and this path can't pass through w since d(w,x)=2. The result follows from this.

(7) Note that λ≤1 implies that any adjacent points can have at most one common neighbor. Both of the graphs indicated contain adjacent points with 2 common neighbors, and therefore can't exist as subgraphs of G.

Remark 2.2. In reference to (6) in Lemma 2.1, much more is known. A strongly regular graph is in fact k-connected: the removal of any k-1 vertices does not disconnect the graph, and in fact the only set of k vertices whose removal does disconnect the graph is the neighborhood of a vertex. This is non-trivial, though; see [9].

The friendship graph, denoted by Fn, is n copies of K3 conjoined at a common vertex. Note that Fn is a planar graph with 2n+1 vertices and 3n edges [20]. The following result gives a local characterization of strongly regular graphs with λ=1.

Lemma 2.3. Let G be a connected strongly regular graph with parameters (n,k,1,μ). Then every vertex together with its neighbours form a friendship graph with k/2+1 vertices.

Proof. Note that the handshake lemma implies k is even. Consider an arbitrary vertex u in G. Since G is connected, there exists an edge incident to u and by hypothesis that edge belongs to a K3. G≠K3 and regular implies that there exists another edge incident to u but disjoint from the first triangle. But by 7 of the previous lemma, diamonds are forbidden in G and hence that edge also belongs to another K3. Proceeding like this we find that u together with its neighbours form a friendship graph with k/2+1 vertices.

A wheel graph Wn is formed by joining a single vertex to all vertices of the n-cycle Cn. The following result indicates a structural characteristic of strongly regular graphs with λ≥2.

Lemma 2.4. Let G be a connected strongly graph with parameters (n,k,λ,μ) with λ≥2. Then every vertex is a central vertex of at least one wheel.

Proof. Since λ≥2, given an edge e the endpoints have at least 2 common neighbors, and e together with these two paths of length 2 form a diamond. Consider u∈V(G), and let e1 be any edge incident to u. e1 is then the central edge of a diamond. Let e2 and e3 be the other edges of the diamond which are incident to u. Then there exist diamonds with e2 and e3 as their central edges. We proceed like this, and the process will terminate only when u together with some set of edges form a wheel. It may happen that there exists another edge incident to u which is not in the above wheel. In this case by the same argument we can find another wheel with u as the central vertex.

The following indicates the advantages enjoyed by requiring graphs to be edge-regular (or strongly regular) rather than just regular. We reiterate that this result is false for regular graphs which are not edge-regular.

Theorem 3.1. If G is an edge-regular graph with parameters (n,k,λ), then Γ(G) and Δ(G) are regular graphs.

Proof. Consider an arbitrary vertex x of Γ(G). Let uv be the edge corresponding to this vertex in G. Then by the definition of Γ(G), the degree of x is dΓ(G)(x)=dG(u)+dG(v)-2|N1(u)∩N1(v)|-2, where dΓ(G)(x) denotes the degree of x in Γ(G) and dG(u),dG(v) denote the degrees of u,v in G. Hence Γ(G) is 2(k-λ-1)-regular.

Now consider an arbitrary vertex x in Δ(G). Let e=uv be the corresponding edge in G. Then the degree of x in Δ(G) is 2|N1(u)∩N1(v)|=2λ. Therefore, Δ(G) is 2λ-regular.

We are interested in even stronger statements. In particular, we are interested in conditions under which the Gallai and anti-Gallai graphs are edge-regular, or even strongly regular. We will consider each of these separately in the following two subsections.

3.1. Gallai graphs

As per Theorem 3.1 we have that if G is strongly regular then Γ(G) is regular. In this section we prove that the Gallai graphs of some special classes of strongly regular graphs are edge-regular or strongly regular. We begin with a more general structure theorem.

Theorem 3.2. Let G be a connected graph. The Gallai graph Γ(G) is disconnected if and only if there exists a partitioning of the edge set E(G) into sets E1,E2,...Ep (where p≥2) such that ei∈Ei and ej∈Ej being incident in G implies that ei and ej span a triangle in G.

Proof. Suppose that Γ(G) is disconnected and let Γ1,Γ2,...Γp with p≥2 be the components of Γ(G). Let Ei={e∈G : e is an edge corresponding to a vertex v in Γi}, where 1≤i≤p. Clearly, Ei is a partition for E(G). Since the connectedness of G implies the connectedness of L(G), at least one edge of Ei is incident with some e∈Ej for some j≠i. But, Γi and Γj are different components of Γ(G), and hence if ei∈Ei is incident with ej∈Ej then they must span a triangle in G.

For the converse assume that such a partition exists for E(G). Then, for any distinct i and j, the vertices corresponding to the edges in Ei and Ej are in different components in Γ(G).

We can say more in special cases. For instance, for λ=0 we have the following.

Theorem 3.3. Let G be a connected strongly regular graph with parameters (n,k,0,μ). Then Γ(G) is connected and edge-regular. Also it is strongly regular if and only if the following conditions hold:

• (1)

  If μ=1 then any two non-adjacent edges belong to a common C5.

• (2)

  If μ>1 then any two non-adjacent edges belong to a common C4.

Proof. Since λ=0, G is K3-free and thus Γ(G)≅L(G). Since G is connected and k-regular, L(G) is connected and 2k-2 regular, and thus so is Γ(G).

Consider two adjacent vertices x and y in L(G), and let e1 and e2 be the corresponding edges in G. Then e1 and e2 must have a common vertex in G. The number of common vertices of x and y in L(G) is same as the number of edges incident on the common vertex of both e1 and e2. Since the graph is k-regular it is equal to k-2. Hence Γ(G) is an edge-regular graph with parameters (nk2,2k-2,k-2).

Now consider two non-adjacent vertices x and y in L(G). Let f1 and f2 be the corresponding edges in G. Then f1 and f2 have no common vertex in G. The number of common vertices of x and y in L(G) is same as the number of edges adjacent to both f1 and f2.

If μ=1, by Lemma 2.1 part 4, f1 and f2 belong to a cycle of length at most 6 (the other possibility, that one point is adjacent to all endpoints of f1 and f2, is not possible since λ=0). The cycle cannot be of length 3 (because λ=0) or 4 (because μ=1). If the cycle is of length 5, then the number of common vertices of x and y is 1, otherwise it is 0. Since G is strongly regular by Lemma 2.1 part 3 there exist non adjacent edges which belong to a C5. So L(G) is strongly regular if and only if any two non-adjacent edges belong to a C5.

We should note that if μ=1 then G is a Moore graph, and there is a well-known classification of such graphs (see [17]). G is therefore C5, the Petersen graph, the Hoffman-Singleton graph, or the famous hypothetical Moore graph of valency 57. Of these, C5 is the only one such that any two non-adjacent edges belong to a common C5.

The same reasoning applies if μ>1, except that now f1 and f2 may belong to C4,C5 or C6. If f1 and f2 belong to C4 then the number of common vertices of x and y is 2; otherwise it is 1 or 0. Since μ>1, in G there are edges which belong to C4. So Γ(G) is strongly regular if and only if any two non-adjacent edges belong to a C4.

We also have the following result when λ=1.

Theorem 3.4. If G is a connected strongly regular graph with parameters (n,k,1,μ), then Γ(G) is edge-regular but not strongly regular.

Proof. Since G is strongly regular, Γ(G) is 2(k-2)-regular by Theorem 3.1. Now consider two adjacent vertices v1 and v2 in Γ(G). If e1 and e2 be the corresponding edges in G, then the number of common vertices of v1 and v2 is same as the number of induced K1,3's in which e1 and e2 are present. By Lemma 2.3, since the number of such induced K1,3 is k-2, any two adjacent vertices have k-2 common neighbours. Hence Γ(G) is an edge-regular graph with parameters (nk2,2k-4,k-2).

To prove that Γ(G) is strongly regular, consider two vertices v1 and v2 which are non-adjacent in Γ(G). Let e1 and e2 be the corresponding edges in G. Then in G either e1 and e2 span a triangle or e1 and e2 are non-adjacent.

In the first case, the number of common neighbours of v1 and v2 is same as the number of edges which form K1,2 with both e1 and e2. By Lemma 2.3 it is same as k-2.

In the latter case, the number of common vertices is same as the number of induced P4's with end edges e1 and e2. To find the number of induced P4's we consider the following cases.

1) μ=1

2) μ>1

If μ=1 by Observation 3, e1 and e2 may belong to a C5 or C6. By Observation 5, C4's are forbidden in G. Therefore the number of such induced P4 is one if e1 and e2 belong to a C5; otherwise it is zero. Since G contains C5, Γ(G) is strongly regular if and only if k-2=1 and any two non-adjacent edges belong to at least one C5. But this is not possible since k is an even number by Lemma 2.3.

If μ>1, by the same argument in the above theorem Γ(G) is strongly regular if and only if k-2=2 and any two edges belong in a C4. Hence we conclude that Γ(G) is strongly regular if and only if k=4,μ>1 and any two non-adjacent edges belong to a C4. However, the strongly regular graphs of valency 4 are known, and can be found in [8]. They are the octahedron (with λ=2), the complete bitartite graph K3,3 (with λ=0), and the 3×3 grid (which has non-adjacent edges not belonging to a C4, as may be easily checked). Therefore there are no strongly regular graphs satisfying this requirement, and the theorem follows.

Furthermore, we can deduce a result on the connectivity of Γ(G) under the same conditions as for the previous two results.

Theorem 3.5. Let G be a connected strongly regular graph with parameters (n,k,λ,μ). Suppose that λ=0 or 1. Then Γ(G) is 2-connected.

Proof. We have the following cases.

Case 1: λ=0

Since G is K3-free, Γ(G)≅L(G). When we consider any two vertices of L(G), by Lemma 2.1 Part 4, the corresponding edges belong to a C4,C5 or C6 (there can't be a vertex adjacent to all endpoints of the corresponding edges, since G is K3-free). So in L(G) any two vertices belong to a C4,C5 or C6. Hence it is 2-connected.

Case 2: λ=1

In order to show that Γ(G) is 2-connected it is enough to show that any two vertices in Γ(G) belong to a cycle. Consider two vertices x and x' in Γ(G). We consider separately the following cases.

(1) xx' is an edge in Γ(G).

(2) xx' is not an edge in Γ(G).

Subcase A: xx' is an edge in Γ(G) implies that the corresponding edges e and e' are incident in G and do not belong to a K3. By Lemma 2.3 there exists an edge l such that e and l span a K3 in G. Similarly there exists edge l' such that e' and l' span a K3 in G. Then the vertices corresponding to e,l',l,e' form a path P4 in Γ(G). Then this path together with the edge xx' form a C4 in Γ(G).

Figure 2 shows the edges used in this argument to form a cycle in Γ(G). The reader may wish to take the time to thoroughly digest this argument, as variants of it will be used throughout the next subcase.

Figure 2. Edges forming a C4 in Γ(G)

Subcase B: xx' not an edge in Γ(G), which means that either the corresponding edges are incident in G and belong to a K3 or are not incident. For the first case, by Lemma 2.3, there exist at-least two edges l and l' which span a K3 in G. Then the vertices corresponding to e,l,e',l',e span a C4 in Γ(G). For the latter case by Lemma 2.1 part 4, either e and e' belong to a cycle Cn where 3<n<7 in G, or there is a vertex adjacent to all endpoints of e,e'. Let us consider the cycle case first. If it is an induced Cn then clearly x and x' belong to a Cn in Γ(G). If not, there are edges which belong to a K3 in G. Consider two edges e1 and e2 with a common vertex u and span a K3 in G. By Lemma 2.3 there exist another edges l and l' incident on u which span a K3 in G. Since diamonds are forbidden in G, the vertices corresponding to e1,l,e2 form a P3 in G. So, if two edges span a K3 in G then by the above explanation we can find an edge such that the vertices corresponding to the edges of K3 and the new edge form a P3 in G. Also if e1,e2,e3 are three consecutive edges in Cn and if e1 and e2 span a K3 in G, since diamonds are forbidden in G, e2 and e3 cannot span a K3 in G. So by the above explanation in Γ(G), we can find a cycle Cn of length at most 9 containing the vertices x and x'. That is, in Γ(G) any two vertices belong to at least one Cn. Hence Γ(G) is 2-connected.

Finally, if there is a vertex v adjacent to each endpoint of e and e' then a similar argument allows us to build a cycle in Γ(G), as follows. Since k≥4 each endpoint of e is adjacent to a point other than v, and this can't be an endpoint of e' since diamonds are forbidden. This new edge cannot span a triangle with e or containing v, since λ=1. Similar new edges can be found at the endpoints of e'. The edges ef1s1s'2f'2e'f'1s'1s2f2e form a C10 in Γ(G).

3.2. Anti-Gallai Graphs

The following is the analogue of Theorem 3.2 for anti-Gallai graphs.

Theorem 3.6. Let G be a connected graph. The anti-Gallai graph Δ(G) is disconnected if and only if there exists a partition of the edge set of G into E1,E2,...Ep where p≥2, such that if ei∈Ei and ej∈Ej are incident in G then ei and ej do not belong to a K3, and there exists at least one pair of this type.

Proof. Suppose that Δ(G) is disconnected and let Δ1,Δ2,...Δp with p≥2 be the components of Δ(G). As in the proof of Theorem 3.2 consider

where 1≤i≤p. Clearly, Ei is a partition for E(G). Since the connectedness of G implies the connectedness of Ł(G), at least one edge ei∈Ei is incident with some ej∈Ej with j≠i. However, Δi and Δj are different components of Δ(G), and hence if ei∈Ei is incident with ej∈Ej then they do not belong to a triangle in G.

For the converse assume that such a partition exists for E(G). Then for any i and j, the vertices corresponding to the edges in Ei and Ej induce different components in Δ(G).

We can deduce from this a result on strongly regular graphs with λ=2 which are locally cycles, which are graphs such that the subgraph induced on N1(x) for any x is a cycle. A prominent example of a graph of this type is the Shirkhande graph, which has parameters (16,6,2,2). The result is as follows.

Theorem 3.7. Let G be a connected strongly regular graph with parameters (n,k,2,μ) which is locally a cycle. Then Δ(G) is connected and edge-regular.

Proof. Suppose Δ(G) is disconnected. Then by Theorem 3.6 there exists at least two edges ei∈Ei and ej∈Ej which are incident but do not belong to a K3 in G. Let u be the common vertex of both ei and ej. By assumption, since the neighbouring vertices induce a wheel in G, there exist edges ei+1,ei+2,...,ej-1,ej such that the pairs of edges (ei,ei+1),(ei+1,ei+2),...,(ej-1,ej) belongs to a K3 in G. Since ei∈Ei, the edges ei+1,ei+2,...,ej-1,ej all belong to Ei. This is a contradiction, and hence Δ(G) is connected.

By Theorem 3.1, Δ(G) is a 4-regular graph. Since G is not K4 any two adjacent vertices in Δ(G) have only one common neighbour. Hence Δ(G) is edge-regular with parameters (nk2,4,1).

The following is a series of examples illustrating our results.

Example 3.8. Let G be a connected strongly regular graph with parameters (n,k,0,μ). Since λ=0, G is K3-free. Hence Δ(G) is totally disconnected. The spectrum of Δ(G) is (0kn2).

Example 3.9. Let G be a connected strongly regular graph with parameters (n,k,1,μ). Since λ=1, every edge of G belong to exactly one K3 and no two K3 share a common edge. Therefore Δ(G) is the disjoint union of kn6 triangles. Δ(G) therefore has the spectrum −1kn3,2kn6.

Example 3.10. Let us consider the anti-Gallai graph of the line graph of the complete bipartite graph, L(Kn,n). L(Kn,n) contains 2n copies of Kn sharing common vertices, where two Kn's have no common edges and the edges of two copies of Kn do not belong to a K3. Hence Δ(L(Kn,n)) is the disjoint union of 2n copies of Δ(Kn). Since every pair of edges in Kn spans a triangle, Δ(Kn)≅L(Kn), and L(Kn) is a well-known family of graphs known as the triangular graphs. These are strongly regular with parameters (n(n-1)2,2(n-2),n-2,4) and spectrum (2(n-2)1,(n-4)n-1,-2n(n-3)/2). Hence the spectrum of Δ(L(Kn,n)) is (2(n-2)2n,(n-4)2n(n-1),-2n2(n-3)).

Our final result applies to a situation in which we are not able to identify Δ(G) easily but in which we can say something about the spectrum only.

Definition 3.11. Suppose α1≤…≤αn and β1≤…≤βm, with m<n. We will say the sequence of β's interlace the sequence of α's if αk≤βk≤αk+n-m for k=1,…,m.

The following two lemmas are famous results in spectral graph theory.

Lemma 3.12. [12] Let G be a graph and H an induced subgraph of G. Then the eigenvalues of H interlace those of G.

Lemma 3.13. [5] If G is a k-regular graph, then spec(G)∈[-k,k], and k∈spec(G).

We need two further definitions.

Definition 3.14. Let G1 and G2 be vertex-disjoint graphs. The join of G1 and G2, denoted G1∨G2, is the supergraph of G1+G2 in which each vertex of G1 is adjacent to every vertex of G2 [5].

Definition 3.15. The semi-total point graph R(G) of a graph G is obtained from G by adding a new vertex corresponding to every edge of G, then joining each new vertex to the end vertices of the corresponding edge i.e; each edge of G is replaced by a triangle [28].

The semi-total point graph of a cycle, R(Cn), will be of special interest to us, and Figure 3 represents this graph for n=6.

Figure 3. R(C6)

The following lemma connects joins, semi-total point graphs, and anti-Gallai graphs.

Lemma 3.16. [24] If G=H∨K1, where H is K3-free, then Δ(G) is the semi-total point graph of H.

We are now prepared to prove the following theorem.

Theorem 3.17. Let G be a connected strongly regular graph with parameters (n,k,2,μ) which is locally a cycle. Then spec(Δ(G))⊆[-4,4] and the eigenvalues of R(Ck) interlace those of Δ(G).

Proof. By Theorem 3.7, Δ(G) is a 4-regular graph. Therefore, by Lemma 3.13 [5] the largest eigenvalue of Δ(G) is 4 and spec(G)∈[-4,4]. Also, by assumption each vertex belong to exactly one wheel (Cn∨K1). Since λ=2, a vertex in G together with its neighbours form an induced k-wheel. Then, by Lemma 3.16 [24], it is clear that Δ(G) contains the semi-total point graph R(Ck) as an induced subgraph. Therefore, by Lemma 3.12 [12], the eigenvalues of R(Ck) interlace those of Δ(G).

To apply this result requires knowledge of the spectrum of R(Ck). The eigenvectors of this graph can be found in a similar manner to that of a cycle, namely by placing powers of a complex n-th root of unity at the points of the cycle, and then finding what the remaining values must be at the other points. We omit the details, but the reader may check that the spectrum of R(Ck) is the values of the form r±r2+4r+82, where r=2cos(2πk/n) for k=1,…,n.

We would like to thank Misha Lavrov for helpful conversations, and an anonymous referee for useful comments.