Combined voltage assignments, factored lifts, and their spectra
C. Dalfó M. A. Fiol S. Pavlíková J. Širáň



	


Combined voltage assignments,
 factored lifts, and their spectra

    C. Dalfó^a, M. A. Fiol^b,  S. Pavlíková^c, and J. Širáň^d

		

		^aDepartament. de Matemàtica
 Universitat de Lleida, Igualada (Barcelona), Catalonia

		cristina.dalfo@udl.cat

		^bDepartament de Matemàtiques

  Universitat Politècnica de Catalunya, Barcelona, Catalonia 

		Barcelona Graduate School of Mathematics 

		Institut de Matemàtiques de la UPC-BarcelonaTech (IMTech)

		miguel.angel.fiol@upc.edu

        ^c Inst. of Information Engineering, Automation, and Math., FCFT, 

   Slovak Technical University, Bratislava, Slovakia

		sona.pavlikova@stuba.sk 

   Department of Mathematics and Descriptive Geometry, SvF

   Slovak University of Technology, Bratislava, Slovak Republic

		jozef.siran@stuba.sk
 
    
===============================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================



§ ABSTRACT 
We consider lifting eigenvalues and eigenvectors of graphs to their factored lifts, derived by means of a  
combined voltage assignment in a group. The latter extends the concept of (ordinary) voltage assignments known from regular coverings and corresponds to the cases of generalized covers of Potočnik and Toledo (2021) in which a group of automorphisms of a lift acts freely on its arc set. With the help of group representations and certain matrices over complex group rings associated with the graphs to be lifted, we develop a method for the determination of the complete spectra of the factored lift graphs and derive a sufficient condition for lifting eigenvectors. 

.5cm		
Keywords : Lift graph, voltage assignment, group representation, spectrum.

MSC 2020 : 05C25, 05C50.






§ INTRODUCTION



A well-known and prolific construction of new graphs from old relies on (regular) graph covers, made popular in the past through the monograph by Gross and Tucker <cit.>. Algebraically, one starts with a `base graph' equipped with a `voltage assignment' on its arcs in a group, which gives rise to an `ordinary lift' with vertex- and edge-set being a product of the vertex- and edge-set of the base graph with the voltage group, and with incidence defined in such a way that the voltage group acts freely on the vertex-set of the lift. 

Conversely, if one has a graph with a group of automorphisms acting freely on vertices, then the graph arises as a regular lift as indicated (and the base graph is simply a quotient of the given graph by its group of automorphisms in question). Notable examples of such a situation are Cayley graphs, which admit a group of automorphisms acting regularly on the vertex set, being thus ordinary lifts of one-vertex graphs with loops and/or semi-edges attached.
 
The versatility of ordinary lift graphs is exemplified across various research areas of graph theory, spanning fundamental problems like the degree/diameter problem to intricate theorems such as the Map Color Theorem. The advantages of covering construction lie in the fact that, in a number of important situations, the properties of the lift can be conveniently expressed in terms of the properties of a base graph and the voltage assignment. 

A notable advancement in understanding lift graphs is the methodology developed by some of the authors alongside Miller and Ryan <cit.>, enabling the determination of spectrum and eigenvectors. Subsequent extensions of this method encompass its adaptation to digraphs <cit.>, its generalization to arbitrary lifts of graphs <cit.>, and its further expansion to deal with the universal adjacency matrix of such lifts <cit.>.

Our aim is to further extend these advancements by introducing the concept of a `factored lift,' which is motivated by replacing the free action of a subgroup of automorphisms on the vertex set in the description of ordinary lifts with a free action on the arc set. Such a viewpoint is a special but important case of the recently developed general approach to coverings by Potočnik and Toledo <cit.> (allowing arbitrary subgroups of automorphisms). The concept, independently introduced by Reyes, Dalfó, Fiol, and Messegué <cit.> and originally referred to as `overlift', represents a significant generalisation akin to permutation voltage lifts, with implications for broader theoretical and practical applications.

The structure of this paper is as follows. In the next section we give definitions and a formal statement of the equivalence between factored lifts and quotients by a free action of an automorphism group of a graph on its arcs. 
Section <ref> is devoted to lifts of walks and their enumeration. Our main results on lifts of spectra and eigenvectors from base graphs to factored lifts are in Section <ref>. In Section <ref> we illustrate our results on two examples, follows by concluding remarks in Section <ref>.






§ COMBINED VOLTAGE ASSIGNMENTS AND FACTORED LIFTS



Let Γ be a finite graph with vertex set V=V(Γ) and arc set A=A(Γ), and let G be a finite group.  Let α: A→ G be a voltage assignment on Γ in the usual sense <cit.>, that is, with α satisfying α(a^-)=α(a)^-1 for any arc a∈ A and its reverse a^-. Let ω be a function assigning to every vertex u∈ V a subgroup G_u of G. The pair (α,ω) is a combined voltage assignment on the base graph Γ, and the graph thus becomes a combined voltage graph, with voltage group G.

The factored lift Γ^(α,ω) is a graph with vertex set V^(α,ω) consisting of all pairs (u,H), where u∈ V and H∈ G/G_u = {hG_u | h∈ G}, the set of left cosets of G_u in G. The arc set A^(α, ω) of the factored lift is defined as follows. For a pair u,v∈ V of adjacent vertices in the base graph Γ, let uv denote the set of arcs of Γ emanating from u and terminating at v (not necessarily distinct from u). Let a∈uv be an arc carrying a voltage α(a)∈ G. Then, for every h∈ G, the arc a together with the element h determine a unique arc (a,h)∈ A^(α, ω) in the factored lift, emanating from the vertex (u,hG_u)∈ V^(α,ω) and terminating at the vertex (v,hα(a)G_v)∈ V^(α, ω). Equivalently, if a∈uv is an arc in the base graph Γ carrying voltage α(a)∈ G and if H∈ G/G_u and K∈ G/G_v are left cosets, then

    (u,H)[](a,h) (v,K)  for every  h∈ H   and each K   such that  hα(a)∈ K .


As a simple example, Fig. <ref> shows a combined voltage graph on the cyclic group _4 (on the left) and the resulting factored lift (the graph of an octahedron) in the centre.



If the subgroup G_u < G is trivial for every vertex u of Γ, a factored lift reduces to an ordinary lift Γ^α with vertex set V^α = {(u,h) | u∈ V, h∈ G}, in which for every arc a ∈uv of Γ and every h∈ G the pair (a,h) is an arc in the ordinary lift Γ^α from the vertex (u,h) to the vertex (v,hα(a)), see Gross and Tucker <cit.>. The way a factored lift Γ^(α,ω) arises from an ordinary lift Γ^α should now be obvious. Indeed, for a general assignment ω: u↦ G_u and for every u∈ V one identifies left G_u-orbits in the fibre {(u,h) | h∈ G} of Γ^α to form vertices (u,hG_u), but making no identification among the existing arcs. This process can be regarded as a `factorisation' induced by `local left actions' of the subgroups G_u<G for u∈ V; hence the term factored lift.

To illustrate this by the example of Figure <ref>, if all the vertices of the voltage graph are assigned the trivial group, the obtained (standard) lift graph is shown in Figure <ref> (right). The factored lift in the middle of Figure <ref> is then obtained by identifying the pairs {(v,0),(v,2)} and {(v,1),(v,3)} to a single vertex each, resulting in the graph of an octahedron.










The factorisation induces a graph epimorphism f: Γ^α→Γ^(α,ω), given simply by (u,h) ↦ (u,H) for H∈ G/G_u such that h∈ H (we have deliberately replaced g by h in the notation for future use). A more detailed description of the action of f is on the following diagram:


    [        (u,h)        (a,h)    (v,hα(a));                                       ;           ↓f                        ↓f;     (u,hG_u)        (a,h) (v,hα(a)G_v) ]


This factorisation results in [G:G_u] vertices of the form (u,H) for left cosets H of G_u in G, each as an f-image of the |G_u| vertices (u,h) for h∈ H. Every vertex (u,H) then has valency |G_u|d_u, where d_u is the valency of u in Γ. Moreover, the group G acts on the factored lift Γ^(α,ω) by left multiplication as a subgroup of automorphisms. The action is free on the arc set A^(α,ω), and is transitive on every fibre F(u)={(u,H)∈ V^(α, ω) | H∈ G/G_u}, with G_u being the stabiliser of the vertex (u,G_u)∈ V^(α,ω) for every u∈ V. In particular, this action of G produces the base graph Γ as a G-quotient of its factored lift; formally, it gives rise to a graph isomorphism Γ≅Γ^(α, ω)/G.

We remark that combining left cosets of G with right multiplication of elements of G by α(a) in (<ref>) is essential for the algebra in the factorisation and morphisms to work.

Factored lifts turn out to be a special case of the generalised voltage assignments and lifts, introduced by Potočnik and Toledo <cit.>, where the objects assigned to arcs are also allowed to be cosets of the voltage group rather than individual elements of this group. In this generalisation, both vertices and arcs of a lift are `indexed' by subgroups of the voltage groups, subject to several technical conditions. The difference between our treatment and the (more general) one in <cit.> is the use of right cosets and left multiplication by voltages in <cit.> versus left cosets and right multiplication by voltages in (<ref>); the latter agrees with the way ordinary voltage graphs and lifts have been introduced in the monograph by Gross and Tucker <cit.>. We refer the interested reader to <cit.> for more details; here, we state a version of Theorem 4 of <cit.> that applies to our setting.


Let Γ^* be a graph and let G be a group of automorphisms of Γ^* that acts freely on the arcs of the graph. Then, on the quotient graph Γ=Γ^*/G with vertex set V and arc set A there exists a voltage assignment α: A→ G with the property that α(a^-) = α(a)^-1 and a function ω that assigns to every u∈ V a subgroup G_u of G, such that the factored lift Γ^(α, ω) is isomorphic to the original graph Γ^*.


Thus, combined lifts are, on the one hand, a generalisation of ordinary voltage lifts, dealing with a group of automorphisms acting freely on vertices, to the situation of a group of automorphisms acting freely on arcs. On the other hand, combined lifts are a special case of the general lifts of <cit.> that allow for an arbitrary action of a group of automorphisms. For completeness, there is another well-known generalisation of ordinary lifts, which are the so-called relative or permutation lifts, see Gross and Tucker <cit.> and Dalfó,  Fiol, Pavlíková and  Širáň <cit.>. This generalisation, however, is in terms of coverings —it extends consideration of regular coverings arising from ordinary lifts to general coverings— and does not refer to group actions.





§ COUNTING LIFTS OF WALKS



Lifts of walks are of central importance in the study of coverings. In an ordinary lift Γ^α of a base graph Γ with a voltage assignment α in a group G, every walk W in Γ starting at a vertex u lifts, for each h∈ G, to a unique walk W_h in Γ^α starting at the vertex (u,h). Here `lifting' means that the projection π: Γ^α→Γ given by erasing the group coordinate maps arcs of the walk W_h bijectively onto those of W. The situation is, however, a bit different in a factored lift Γ^(α,ω) arising from Γ by a combined voltage assignment (α,ω) in G, and this is what we now aim to explain.

By the definition of a factored lift, for every h∈ G, an arc a∈uv of Γ lifts to the arc (a,h) in Γ^(α,ω) emanating from the vertex (u,hG_u) and terminating at the vertex (v,hα(a)G_v). But for a fixed h and an arbitrary g∈ G_u, every arc of the form (a,hg) emanates from the same vertex (u,hG_u) since hgG_u=hG_u. This way, one obtains |G_u| arcs (a,hg) in the factored lift, all emanating from the vertex (u,hG_u) and projecting onto the arc a of Γ by the same projection π as above.  Note, however, that their terminal vertices (v, hgα(a)G_v) may be different.

 A useful way to look at lifts of arcs by combined voltage assignments is to imagine that every arc a∈uv of the base graph has been assigned a set β of |G_u| voltages of the form β(a) = gα(a) for g∈ G_u, inducing the |G_u| lifts (a,hg) of the arc a, all emanating from the same vertex (u,hG_u) but terminating at possibly distinct vertices (v,hβ(a)G_v)=(v,hgα(a)G_v).


This feature propagates when one continues to follow arcs along a walk in the base graph Γ. To see this, let W=a_1a_2… a_ℓ be a walk of length ℓ in Γ consisting of ℓ consecutive arcs, where a_j∈v_jv_j+1 for j∈ [ℓ] = {1,2,…, ℓ}. Recalling the notation ω(u)=G_u for every vertex u of Γ, let us choose ℓ elements g_j∈ω(v_j) for j∈ [ℓ] in an arbitrary way. Further, let h_1=1 and for j∈ [ℓ] we recursively define h_j+1 = h_jg_j α(a_j). Then, the walk W lifts to a walk W in Γ^(α,ω) of the form

    W = (a_1,h_1g_1)(a_2,h_2g_2)… (a_j,h_jg_j) … (a_ℓ,h_ℓg_ℓ),

where, for every j∈ [ℓ], the arc (a_j,h_jg_j) of Γ^(α,ω) starts at the vertex (v_j,h_jω(v_j)) and ends at the vertex (v_j+1,h_jg_jα(a_j)ω(v_j+1)) coinciding with (v_j+1,h_j+1ω(v_j+1)) due to the definition of the sequence (h_j)_j∈ [ℓ]. It may be checked that every lift of a walk arises this way. In particular, our walk W gives rise to ∏_j∈ [ℓ]|ω(u_j-1)| lifts W in Γ^(α,ω) as in (<ref>), each projecting onto W by π; their count matches the number of choices of elements g_j∈ω(v_j) for j∈ [ℓ]. Note that if ω is a trivial assignment, this gives a generalisation of the unique walk-lifting property for ordinary lifts.

In the special case when the walk W in Γ as above is closed, that is, when v_1=v_ℓ+1, the lift W given by (<ref>) is a closed walk in Γ^(α,ω) if and only if ω (v_ℓ+1)=ω(v_1) and, at the same time, h_ℓ+1∈ω(v_1). But by our recursion (with h_1=1), the last condition means that 

    h_ℓ+1 = g_1α(a_1)g_2α(a_2)… g_ℓα(a_ℓ) ∈ω(v_1) .

Further, as g_1 already belongs to ω(v_1), it follows from (<ref>) that there is an element g̅_1∈ω(v_1) such that

    g̅_1α(a_1)g_2α(a_2)… g_ℓα(a_ℓ) = e,

where e is the unit element of G. Equation (<ref>) may be usefully interpreted by recalling the modified voltages β from Remark <ref>, with values in the sets G_uα(a)={gα(a) | g∈ G_u} for arcs α emanating from u in the base graph. Namely, if one lets  β(a_1)= g̅_1α(a_1) and β(a_j)= g_jα(a_j) for j∈{2,3,…,ℓ}, then the product β(W) = β(a_1)β(a_2) …β(a_ℓ), representing the total voltage (also known as `net' voltage) of the walk W under the assignment β accumulated by multiplying voltages as one moves along arcs of W in Γ, is the unit element e∈ G. Moreover, multiplying equation (<ref>) from the left by an arbitrary element g∈ G_u or a direct reference to (<ref>) gives a one-to-one correspondence between the closed walks in Γ of length ℓ rooted at v_1 that have net voltage e on the one hand, and net voltage g on the other hand. We summarize this observation for future reference.


Let Γ be a base graph equipped with a combined voltage assignment (α,ω) in a group G, and let β be the corresponding `set voltage assignment' on Γ introduced in Remark <ref>. Then, in the factored lift Γ^(α,ω), the lifts of closed base-graph walks W of length ℓ rooted at a vertex u and of net voltage β(W)=g for any particular g∈ G_u are in a one-to-one correspondence with lifts of walks W with the same parameters but with net voltage β(W)=e, the unit element of G.


Our intended study of lifts of eigenvectors and eigenvalues from a combined voltage graph to a factored lift requires introducing further notation, the origins of which come from <cit.>. Given a combined voltage graph =(V,A) of order k under the assignment (α, ω) in a voltage group G we first assign to it a k× k matrix = (;α,ω) indexed with the set V, entries of which are elements of the complex group algebra [G] of G. For every u∈ V, we first introduce a specific element G_u^+ ∈[G] by letting  G_u^+=∑_g∈ G_ug. With this in hand, for every u,v∈ V the (u,v)^ th element of  is defined by

    _u.v = ∑_a∈uvG_u^+α(a) = G_u^+∑_a∈uvα(a)  ,

where, as before, uv is the set of all arcs from u to v in , with _u,v=0 if uv=∅.

The matrix = (;α,ω) associated with a combined voltage graph Γ by (<ref>)  enables us to determine the number of closed walks of a given length and rooted at a given vertex in the factored lift Γ^(α, ω) as follows.



Assume that, for a given ℓ≥ 0, the (u,u)^ th entry of the ℓ^ th power ^ℓ of the matrix =(;α,ω) is equal to the element (^ℓ)_uu=∑_g∈ Gb_g^(ℓ)g of the group algebra [G]. Then, the number n(u,ℓ) of closed walks in the factored lift ^(α,ω),  rooted at a vertex (u,G_u), is equal to

    n(u,ℓ)=|G_u|· b_e^(ℓ),

where e is the identity element of G.



We begin by pointing out that, by (<ref>), every entry of the u^ th row of  is a left multiple by the element G_u^+=∑_g∈ G_ug of the group algebra (G). Because of this, every arc a emanating from a vertex u in  may be viewed as being  equipped with a set of voltages β(a)= G_uα(a) = {gα(a); g∈ G_u} as stated in Remark <ref>. This set of voltages may, in turn, be identified with the element G_u^+α(a) ∈[G] constituting one term in the definition of the entry _u.v for a specific arc a∈uv. For the rest of the argument, assume that a vertex u of Γ has been fixed.

Invoking Remark <ref> again and making use of the obvious interpretation of entries of a power of a matrix, it follows that for g∈ G the coefficient b_g^(ℓ) of the group-algebra element (^ℓ)_uu= ∑_g∈ Gb_g^(ℓ)g is equal to the number of closed walks W in Γ of length ℓ, rooted at u and of net `set voltage' β(W) = g. In particular, for g=e, the coefficient b_e^(ℓ) counts the number of closed walks W in Γ of length ℓ, rooted at u but with trivial net voltage β(W)=e. But such walks are in a one-to-one correspondence with closed walks of length ℓ in Γ^(α,β), rooted at the vertex (u,G_u), and having the form (<ref>) for v_1=u, with g_1 replaced by g̅_1 from (<ref>) to have net voltage e in the projection to Γ. Finally, by Remark <ref>, there is a one-to-one correspondence between closed walks of length ℓ rooted at (u,G_u) in the factored lift, with projections onto the base graph having net voltages respectively e and g for an arbitrary g∈ G_u. This translates to the fact that b_e^(ℓ) = b_g^(ℓ) for every g∈ G_u and so the number of closed walks of length ℓ in the factored lift, rooted at a vertex (u,G_u), is equal to |G_u|· b_e^(ℓ), as claimed.    

As an illustration of Proposition <ref>, consider again the example of Figure <ref> for the cyclic voltage group G=_4=⟨ g | g^4=e⟩ with G_u={e} and G_v={e,g^2}. The matrix  from (<ref>) associated with the combined voltage graph on the left-hand side of Figure <ref> has the form

    =(
    [          g+g^-1             e+g; (e+g^2)(e+g^-1)               0 ])=(
    [       g+g^-1          e+g; e+g+g^-1+g^2            0 ]).

Taking ℓ=5, one may check that (^5)_uu=176g^3+160g^2+176g+160 and (^5)_vv=80g^3+80g^2+80g+80. By Proposition <ref>, for the number of closed walks rooted at (u,G_u) and at (v,G_v) in the factored lift one obtains n(u,5)=|G_u|· b_e^(5)=1·160=160 and n(v,5)=|G_v|· b_e^(5)=2· 80=160. The two values coincide as the factored lift is vertex-transitive.






§ VOLTAGE GROUP REPRESENTATIONS, LIFTS OF SPECTRA




To explain connections between factored lifts and representations of voltage groups, let Γ=(V,A) be a base graph of order k with a combined voltage assignment (α,β) in a group G. Let ρ be a complex irreducible representation of G in ℂ^d of dimension d=d(ρ). Recalling the matrix =(; α, β) defined by (<ref>) in the previous section, we now link this matrix with the representation ρ by introducing a dk× dk complex block matrix (ρ). For every ordered pair (u,v) of vertices of V the  (u,v)^ th block entry of (ρ) is defined to be the d× d matrix

    _u,v(ρ) = ∑_a∈uv ∑_h∈ G_u ρ(hα(a)),

where the sum of matrices is defined in the usual way; the block entry _u,v(ρ) is the all-zero d× d matrix if uv=∅. (We will assume throughout that the indexation within the d× d blocks of _u,v(ρ) by the set {1,2,…,d} is the same across all the k^2 blocks of this kind, which themselves are indexed by pairs of elements of V.)

In order to simplify the forthcoming calculations, for G_u and its [G]-variant G_u^+ = ∑ _g∈ G_u g introduced in the previous section, we let

    ρ(G_u) = ρ(G_u^+) = ∑_h∈ G_uρ(h)  .

Combined with the fact that ρ is a group homomorphism, the notation of (<ref>) enables one to rewrite the defining equation (<ref>) in the form

    _u,v(ρ) = ρ(G_u) ∑_a∈uvρ(α(a)),

which can be advantageously interpreted by saying that the u^ th row of the matrix (ρ) is a left multiple by the d× d factor ρ(G_u) which is `constant' for any fixed u∈ V.

In fact, when ρ_0 is the trivial representation, then (ρ_0) is a quotient matrix of a regular (or equitable) partition of the factored lift graph, where cells correspond to fibres F(u)={(u,H)∈ V^(α, ω) | H∈ G/G_u} introduced in the previous section; see the example in Figure <ref>. In particular, the largest eigenvalue of (ρ_0) corresponds to the spectral radius of the factored lift.

To work with group representations, let (G) be a complete set of irreducible representations of a finite group G. Let H<G be an arbitrary subgroup of G and, for any ρ∈(G) with dimension d(ρ), let ρ(H) = ∑_h∈ Hρ(h). That is, ρ(H) is the sum of d(ρ)-dimensional complex matrices ρ(h) taken over all elements h∈ H. We note that, in general, ρ(H) may be the zero-matrix, although, of course, all the matrices ρ(h) for h∈ H are non-singular. We make use of the following result of <cit.> obtained earlier by the authors of the present paper.



For every group G and every subgroup H<G of index n=[G:H] one has

    ∑_ρ∈(G)
    d(ρ)·(ρ(H)) = n.



We also need some preparation for working with column vectors of dimension a multiple of d, say, dℓ for some ℓ≥ 1. A complex vector  of dimension dℓ will be represented in the form ^⊤=(_1,_2, …,_ℓ)^⊤, where, for t∈ [ℓ] = {1,2,…,ℓ}, each _t is a d-dimensional column vector called a d-segment of . For such a vector  of dimension dℓ and for every j∈ [d]={1,2,…, d}, the j-section of  will be the ℓ-dimensional column vector _[j] given by _[j]^⊤= (_1,j, _2,j, …,_ℓ,j)^⊤, where _t,j is the j-th coordinate of _t for each t∈ [ℓ].

Suppose now that a dk-dimensional complex column vector  is an eigenvector of our dk× dk matrix (ρ) for some complex eigenvalue λ. Assuming consistent indexation of d× d blocks of (ρ) and d-segments of  by the vertex set V, for every v∈ V the v^ th d-segment of  will be denoted (v).

It remains to introduce a condition for eigenvectors, which we refer to in what follows. We say that, for a d-dimensional representation ρ of G, an eigenvector  for some eigenvalue of the dk× dk dimensional matrix (ρ) satisfies the condition (C) if the following is fulfilled:

    (C)

where _̧v is a d-dimensional column vector that may depend on v but is constant over the elements h∈ G_v. The important fact is that the condition (C) implies that the dk^ω-dimensional vector ^+, with k^ω d-segments indexed by k^ω ordered pairs (v,hG_v) for v∈ V and hG_v∈ G/G_v, given by ^+(v,hG_v) = ρ(h)(v), is well defined and does not depend on representatives of cosets in G/G_v.

We are now ready to state and prove our first result, linking eigenvectors and eigenvalues of a factored lift with representations of its voltage group.



Let  be a graph on a set V of k vertices, with a combined voltage assignment (α,ω) in a finite group G that assigns a subgroup G_v of G to every vertex v∈ G, and let k^ω = ∑_v∈ V[G:G_v] be the number of vertices of the factored lift ^(α,ω). Let ρ be a complex irreducible representation of G of dimension d≥ 1 and let (ρ) be the associated complex dk× dk matrix defined by (<ref>). Further, let  be a dk-dimensional eigenvector of (ρ) for some complex eigenvalue λ of (ρ), with d-blocks (v) for v∈ V, which fulfils the condition (C). Then:


  (i)
The dk^ω-dimensional vector ^+ with k^ω d-segments indexed by k^ω ordered pairs (v,hG_v) for v∈ V and hG_v∈ G/G_v, given by ^+(v,hG_v) = ρ(h)(v), is well defined and does not depend on representatives of cosets in G/G_v.

  (ii)
For every j∈ [d] the j-section ^+_[j] of ^+ is a k^ω-dimensional eigenvector of the factored lift ^(α,ω) for the same eigenvalue λ as above.

  (iii)
Let S be the system of k^ω linear equations of the form cρ(h)(v) = 0 for v∈ V and hG_v∈ G/G_v for an unknown row vector c=(c_1,c_2,…,c_d) of dimension d. The set of j-sections {^+_[j] | j∈ [d]} is linearly independent if and only if the system S has only a trivial solution c =  0. In particular, this is satisfied if V contains a subset U of d vertices such that the d-segments _u for u∈ U are linearly independent.




Part (i) is a consequence of the condition (C), and so we move onto (ii). Our assumption that  is a column eigenvector of (ρ) for an eigenvalue λ is, with the help of (<ref>), equivalent to stating that the d-segments (v) of  for v∈ V satisfy

    λ(u) = ∑_v∼ u(ρ)_u,v(v) = ∑_v∼ u ρ(G_u) ∑_a∈uvρ(α(a)) (v)

for every vertex u∈ V. We also assume that  satisfies our assumption (C) as stated in (<ref>). For such a λ and  we introduce a new column vector ^+ of dimension dk^ω whose d-segments, indexed by the k^ω pairs (v,gG_v)∈ V^(α,ω), are defined by

    ^+(v,hG_v)= ρ(h)(v)  for every  v∈ V  and every  h∈ G ;

the fact that ^+ is well defined is a direct consequence of the assumption (C). Multiplying (<ref>) by the d× d matrix ρ(g) from the left and using (<ref>) with (<ref>) gives

    λρ(g)(u) =  ∑_v∼ u ∑_a∈uv ∑_h∈ gG_u ρ(h)ρ(α(a)) (v) .

Using now the equations (<ref>), one sees that (<ref>) is equivalent to the statement that

    ^+(u,gG_u) = ∑_v∼ u∑_a∈uv∑_h∈ gG_u^+(v,hα(a)G_v) .

The important conclusion that follows from (<ref>) is that, for every j∈ [d], the j-section ^+_[j] of  is a k^ω-dimensional vector satisfying the equation 

    ^+_[j](u,gG_u) = ∑_v∼ u∑_a∈uv∑_h∈ gG_u^+_[j](v,hα(a)G_v) .

But (<ref>) demonstrated that, for every j∈ [d], the j-section ^+_[j] is an eigenvector of the factored lift ^(α,ω) which belongs to the same eigenvalue λ we started with.


For part (iii), the j-sections ^+_[j] for j∈ [d] form a linearly independent set if and only if the linear combination c_1^+_[1] + c_2^+_[2] + ⋯ + c_d^+_[d] results in a k^ω-dimensional zero vector only in the trivial case, that is, when c = (c_1,c_2,…,c_d) is a zero row vector. This must hold for every d-segment of the j-sections, but since by (<ref>) the (u,gG_u)-th coordinate of ^+_[j] is the j-th coordinate (ρ(g)(u))_j of the d-segment ρ(g)(u), the above linear combination equates to a zero vector if and only if the following system of k^ω equations (for every vertex (u,gG_u) of the factored lift)

    c_1(ρ(g)(u))_1 + c_2(ρ(g)(u))_2 + ⋯ + c_d(ρ(g)(u))_d = 0

has only the trivial solution, namely, the zero row vector c. But the system (<ref>) may simply be rewritten in the form c·ρ(g)·(u) = 0. This implies the validity of the statement (iii), including the particular observation about a subset U of d linearly independent d-segments (u) for u∈ U.


If one is interested only in calculating the spectrum (^(α,β)) of a factored lift, it turns out that it is sufficient to consider the spectra ((ρ)) of the complex matrices (ρ), taken over a complete set of irreducible complex representations ρ of the voltage group G, as our next result shows.



Let (α,ω) be a combined voltage assignment on a graph =(V,A) with k vertices in a group G and let n_u=|G:G_u| for every u∈ V, and with the order of the factored lift ^(α,ω) equal to k^ω= ∑_u∈ Vn_u. Let G have order n, with ν conjugacy classes, and let {ρ_r :  r=0,1,…,ν-1} be a complete set of complex irreducible representations of G, of dimensions d(ρ_r)=d_r, so that ∑_r=0^ν-1d_r^2=n. Let B be the multiset of eigenvalues

    B = ⋃_r=0^ν-1d_r ((ρ_r)).

of cardinality ∑_r=0^ν-1kd_r^2=kn. Then, the following statements hold:


  (i)
The multiset B contains at most k^ω=∑_u∈ Vn_u non-zero eigenvalues.

  (ii)
The spectrum of the factored lift ^(α,ω) is the multiset B∖ Z, where Z is a multiset containing kn-k^ω zeros.




For part (i), let u∈ V be a vertex with voltage subgroup ω(u)=G_u<G. Then, for a given irreducible representation ρ_r of dimension d_r, the u^ th block-row of (ρ_r), which is a d_r× d_rk matrix denoted (ρ_r)_u in what follows, is a multiple of the matrix ρ_r(G_u)=∑_h∈ G_uρ_r(h) by the equation (<ref>). Thus, ((ρ_r)_u)≤(ρ_r(G_u)) and hence, for each u∈ V, the matrix (ρ_r)_u has at most ((ρ_r)_u) non-zero eigenvalues. The number of non-zero eigenvalues of the entire d_rk× d_rk matrix (ρ_r) then does not exceed ∑_u∈ V(ρ_r(G_u)). With the help of Proposition <ref>, this gives at most

    ∑_r=0^ν-1d_r∑_u∈ V(ρ_r(G_u))=
    ∑_u∈ V∑_r=0^ν-1d_r(ρ_r(G_u))=
    ∑_u∈ V[G:G_u]=k^ω

non-zero eigenvalues in the multiset B, as claimed.

To establish (ii), we use the irreducible characters χ_r associated with each irreducible representation of G. Let  be the adjacency matrix of ^(α,ω), with entries a_(u,G_u)(v,G_v) for u,v∈ V. It is well known that the total number of rooted closed walks of length ℓ in the factored lift is equal to the trace of the ℓ^ th power ^ℓ of , with elements a^(ℓ)_(u,G_u)(v,G_v). But the same trace is also equal to the sum of the ℓ^ th powers of the eigenvalues (including multiplicities) of ^ℓ. This implies that

    (^ℓ) =∑_u∈ Vn_u a_(u,G_u)(u,G_u)^(ℓ) =∑_λ∈(^(α,ω))λ^ℓ,

where the middle part of (<ref>) is a consequence of the fact that left multiplication by elements of G induces automorphisms of the factored lift that act transitively on its fibres.   

By Proposition <ref>, the u^ th diagonal entry of ^ℓ is a |G_u|-multiple of the coefficient b_e^(ℓ) at the `identity term' e of the [G]-group ring element (^ℓ)_uu = ∑_g∈ Gb_g^(ℓ)g. On the other hand, in <cit.>, it was proved that, in terms of characters, the same 
`identity' coefficient b_e^(ℓ) admits the following evaluation:

    b_e^(ℓ)=1/n∑_r=0^ν-1d_rχ_r((^ℓ)_uu).

Combining (<ref>) with the aforementioned result of Proposition <ref> gives

    a_(u,G_u)(u,G_u)^(ℓ)=|G_u|b_e^(ℓ)=1/n_u∑_r=0^n-1d_rχ_r((^ℓ)_uu).

Consequently, putting the pieces together and using μ as a variable for eigenvalues of the matrices (ρ_r), one obtains

    ∑_λ∈(^(α,ω))λ^ℓ    =(^ℓ)
    = ∑_u∈ Vn_u a_(u,G_u)(u,G_u)^(ℓ) 
    =∑_u∈ V∑_r=0^ν-1 d_rχ_r((^ℓ)_uu) 
       =∑_r=0^ν-1d_r∑_u∈ V((ρ_r)^ℓ) 
      =∑_r=0^ν-1d_r∑_μ∈(B(ρ_r)^ℓ)μ^ℓ,

where the leftmost sum contains k^ω=∑_u∈ Vn_u terms, as opposed to the formally nk terms of the rightmost sum, but by part (i) one is free to remove kn-k^ω zeros from the last sum without affecting the equality. Hence, since such `adjusted equalities' hold for every ℓ=0,1,…,k^ω-1, the multisets of eigenvalues of the factored lift ^(α,ω) and those in B must coincide up to a multiset Z of kn-k^ω zeros (see, for instance, Gould <cit.>). This completes the proof.
 






§ ILLUSTRATION EXAMPLES





Consider the graph ^(α,ω) shown on the left-hand side of Figure <ref>.


The partition shown in the centre of Figure <ref> indicates that the graph is a factored lift induced by an action of a dihedral group D_3=⟨ a,b | a^3= b^2- (ab)^2=e⟩ of order 6, and the corresponding combined voltage graph Γ is shown on the right-hand side of the same figure. The matrix =(), introduced in general by (<ref>), is in this case the 3× 3 matrix shown in (<ref>):

    =(
    [        0        e        0;        e a+a^-1+b        e;        0        e        0 ]).


A complete set of irreducible complex representations of the group D_3 presented above consists of the trivial and alternating 1-dimensional representations ρ_0 and ρ_1 together with a 2-dimensional representation ρ_2 with ζ a primitive complex 3-rd root of 1; they are all displayed in Table <ref>. To save space, we use the symbols I, Dia(x,y) and Off(x,y) for the identity matrix, a diagonal matrix with entries x,y (from top left to bottom right), and an off-diagonal matrix with entries x,y (from top right to bottom left), all of dimension 2.

In this example one has ω(u)=G_u=D_3, ω(v)=G_v{e} and ω(w)=G_w=⟨ a⟩, so  ρ_0(G_u)=6 and ρ_1(G_u)=0, ρ_0(G_v)=ρ_1(G_v)=1, and ρ_0(G_w)=ρ_1(G_w)=3, while, for example, (ρ_1)_u,v=0 and (ρ_1)_v,v = ρ_1(G_v)(ρ_1(a)+ρ_1(a^-1)+ρ_1(b))=1. The 3× 3 matrices (ρ_0) and (ρ_1) are thus given by

    (ρ_0)=(
     [ 0 6 0; 1 3 1; 0 3 0 ]),    (ρ_1)=(
     [ 0 0 0; 1 1 1; 0 3 0 ]).

The entries of (ρ_2) are determined similarly, bearing in mind that this time they are 2× 2 blocks; for example, (ρ_2)_u,v is the sum of all the six matrices appearing in the last row of Table <ref>. An evaluation of (ρ_2)_u,v gives

    (ρ_2)=(
     [            0            0  ∑_i=0^2 ζ^i  ∑_i=0^2 ζ^i            0            0;            0            0 ∑_i=0^2 ζ^-i ∑_i=0^2 ζ^-i            0            0;            1            0       ζ+ζ^-1            1            1            0;            0            1            1       ζ+ζ^-1            0            1;            0            0  ∑_i=0^2 ζ^i            0            0            0;            0            0            0 ∑_i=0^2 ζ^-i            0            0;              ]).


Eigenvalues and eigenvectors of (ρ_r) for r=0,1,2 are listed in Table <ref>, taking into the account that the non-zero eigenvalues of (ρ_0) and (ρ_1) are, respectively, μ^(0)_1,2= 3(1±√(5))/2 and μ^(1)_1,2= (1±√(13))/2.



Observe that for r=0,1, except for the eigenvalues 0 marked by an additional star (0^*), all the remaining  eigenvalues of (ρ_0) and (ρ_1) satisfy the condition (C) in (<ref>) for d=1, since ρ_0|_G_u=ρ_0|_G_w=ρ_1|_G_w=1. This, however, does not hold for the eigenvector of (ρ_1) that belongs to the starred eigenvalue 0^* because (1)≠ 0 and ρ_1|_G_u≠1 (that is, ρ_1(h)(1) is not constant for h∈ G_u).

The similar happens for the eigenvectors of (ρ_2) with the marked zero eigenvalues (0^*), as neither  ρ_2|_G_u and ρ_2|_G_w are a non-zero constant. On the other hand, the first and last eigenvectors of (ρ_2), that is, those corresponding to the eigenvalues 0 and -2, do satisfy the condition since, in both cases, (u)=(w)=(0,0)^⊤. By Theorem <ref>, these eigenvalues have multiplicity 2 in the factored lift graph.

To see in more detail what happens in the case of the eigenvalue -2 for (ρ_2), the 2-dimensional vectors constituting the corresponding 6-dimensional eigenvector are (u)=(0,0)^⊤, (v)=(-1,1)^⊤, and (w)=(0,0)^⊤; here we use transposes to save space. Following Theorem <ref>, to construct the eigenvectors _1^+ and _2^+ of the factored lift, one subsequently calculates

    ^+(u,G_u)    = ^+(w,G_w) = (0,0)^⊤ ,
    ^+(v,eG_v)    =  I(-1,1)^⊤ = (-1,1)^⊤ ,
    ^+(v,aG_v)    =  Dia(ζ,ζ^-1)(-1,1)^⊤ = (-ζ,ζ^-1)^⊤ ,
    ^+(v,a^2G_v)   =  Dia(ζ^2,ζ^-2)(-1,1)^⊤ = (-ζ^2,ζ^-2)^⊤ ,
    ^+(v,bG_v)    =  Off(1,1)(-1,1)^⊤ = (1,-1)^⊤ ,
    ^+(v,abG_v)    =  Off(ζ,ζ^-1)(-1,1)^⊤ = (ζ,-ζ^-1)^⊤ ,
    ^+(v,a^2bG_v)    =  Off(ζ^2,ζ^-2)(-1,1)^⊤ = (ζ^2,-ζ^-2)^⊤ .

Then, taking the first or the second entries, we obtain _1^+ and _2^+, respectively:

    _1^+   =(0,-1,-ζ,-ζ^2,1,ζ,ζ^2,0,0)^⊤;
    _2^+   =(0,1,ζ^-1,ζ^-2,-1,-ζ^-1,-ζ^-2,0,0)^⊤,

which can be checked to be eigenvectors for the eigenvalue -2 of the factored lift ^(α,ω) of Figure <ref>. In summary, the spectrum of the factored lift ^(α,ω) of Figure <ref> is

    (^(α,ω))={ 3(1+√(5))/2, (1+√(13))/2, 0^[3], (1-√(13))/2, 3(1-√(5))/2,  -2^[2] } .




Consider the graph ^(α,ω) shown on the left-hand side of Figure <ref>.



Thus,   is the 2× 2 matrix shown in (<ref>), where Σ(G_u)=e+b.

    =(
     [ (Σ(G_u))(a+a^-1)           Σ(G_u);                e           a+a^-1 ]).

The matrices (ρ_i) for i=0,1,2 are shown in (<ref>) and (<ref>):

    (ρ_0)=(
     [ 4 2; 1 2;   ]),    (ρ_1)=(
     [ 0 0; 1 2;   ]),


    (ρ_2)=(
     [ ζ+ζ^-1 ζ+ζ^-1      1      1; ζ+ζ^-1 ζ+ζ^-1      1      1;      1      0 ζ+ζ^-1      0;      0      1      0 ζ+ζ^-1 ])=(
     [ -1 -1  1  1; -1 -1  1  1;  1  0 -1  0;  0  1  0 -1 ]).


The corresponding eigenvalues and eigenvectors are listed in Table 
<ref>.



The eigenvector of (ρ_1) not satisfying the condition (C) corresponds again to the eigenvalue 0 with an asterisk. But observe that although the eigenvectors of (ρ_2) corresponding to the eigenvalues 0^+ and 0^++ do not satisfy this condition, their sum, that is, the vector ^*=(1,1,1,1)^⊤ does! This is because ρ_2(h)^*(u) and ρ(h)_2^*(v) are constant for every h∈ gG_u=gG_w={g,gb}. Then, by Theorem <ref>, the sum eigenvector ^*  produces two eigenvectors in the factored lift that correspond to the eigenvalue 0. The same reasoning applies to the eigenvector of the eigenvalue -3 so that it also satisfies the condition (<ref>). This example was chosen to illustrate the interesting feature that may happen: A sum of two eigenvectors for the eigenvalue 0 may satisfy the condition (C) even if neither of the two vectors does.

Finally, the spectrum of the factored lift ^(α,ω) is

    (^(α,ω))={ 3+√(3), 2, 3-√(3), 0^[2], -1^[2], -3^[2] }.



To show that the eigenvectors of the factorized lift Γ^(α,ω) of Figure <ref> 
are linearly independent, we apply part (iii) of Theorem <ref>. Indeed, such eigenvectors are obtained from the matrix product , where  is a 12× 12 matrix with block form

    = (_0  | _1  | _2) = (
    [ _0,1    Ø _1,1    Ø _2,1    Ø _2,2    Ø;    Ø _0,1    Ø _1,1    Ø _2,1    Ø _2,2 ]),

where

    _0,1   =(ρ_0(e),ρ_0(a),ρ_0(a^2),ρ_0(b),ρ_0(ab),ρ_0(a^2b))^⊤
    =(1,1,1,1,1,1)^⊤,
    _1,1   =(ρ_1(e),ρ_1(a),ρ_1(a^2),…,ρ_1(a^2b))^⊤=(1,1,1,-1,-1,-1)^⊤,
    _2,1   =(ρ_2(e)_1,ρ_2(a)_1,ρ_2(a^2)_1,…,ρ_2(a^2b)_1)^⊤
    =
    (
    [   1   z z^2   0   0   0;   0   0   0   1   z z^2 ])^⊤,
    
    _2,2   =(ρ_2(e)_2,ρ_2(a)_2,ρ_2(a^2)_2,…,ρ_2(a^2b)_2)^⊤
    =
    (
    [    0    0    0    1 z^-1 z^-2;    1 z^-1 z^-2    0    0    0 ])^⊤.

Note that, as required in the proof, _2,1 and _2,2 are formed, respectively, out of the first and second rows of the matrices ρ_2(e), ρ_2(a), ρ_2(a^2), and so on. The matrix  in this case is a 12× 12 matrix with block form = (_0,_1,_2), where _0 = _0, _1=_1, and _2 = (_2,_2), so that

    =(
    [ _0  Ø  Ø  Ø;  Ø _1  Ø  Ø;  Ø  Ø _2  Ø;  Ø  Ø  Ø _2 ]).

Here, one needs to be careful about the indexation of rows and columns to align eigenvectors with the corresponding eigenvalues. In accordance with the proof of Theorem <ref>, for each ρ_i∈{ρ_0,ρ_1,ρ_2} of dimension d_i, the  d_i× d_i matrix _i is formed by a choice of the corresponding eigenvectors of ρ_i(). To proceed, we choose to list the eigenvalues in the order 3+√(3), 3-√(3), 2, 0, -1, -3, 0, 0, together with a choice of the corresponding eigenvectors as follows:

    _0 = (
    [ 1+√(3) 1-√(3);      1      1 ]),  _1 = (
    [  0 -2;  1  1 ]),  
    _2 = 
    (
    [  0 -2  1  1;  0 -2  1  0; -1  1  1  1;  1  1  1  0 ]),

where, from left to right, the columns of _0 correspond to eigenvalues 3+√(3) and 3-√(3), the columns of _1 to the eigenvalues 2 and 0, and finally the columns of _2 correspond to the eigenvalues -1, -3,0 and 0, respectively. Then, we get


    =(
    [ 1+√(3) 1-√(3)      0     -2      0     -2      1      1      0     -2      1      0; 1+√(3) 1-√(3)      0     -2      0    -2z      z      z      0 -2z^-1   z^-1      0; 1+√(3) 1-√(3)      0     -2      0  -2z^2    z^2    z^2      0 -2z^-2   z^-2      0; 1+√(3) 1-√(3)      0      2      0     -2      1      0      0     -2      1      1; 1+√(3) 1-√(3)      0      2      0    -2z      z      0      0 -2z^-1   z^-1   z^-1; 1+√(3) 1-√(3)      0      2      0  -2z^2    z^2      0      0 -2z^-2   z^-2   z^-2;      1      1      1      1     -1      1      1      1      1      1      1      0;      1      1      1      1     -z      z      z      z   z^-1   z^-1   z^-1      0;      1      1      1      1   -z^2    z^2    z^2    z^2   z^-2   z^-2   z^-2      0;      1      1     -1     -1      1      1      1      0     -1      1      1      1;      1      1     -1     -1      z      z      z      0  -z^-1   z^-1   z^-1   z^-1;      1      1     -1     -1    z^2    z^2    z^2      0  -z^-2   z^-2   z^-2   z^-2 ]).

Then, the eigenvectors of the lift are obtained, first removing the columns 4,8,12, where the first and fourth rows  (corresponding to the elements of G_u={e,b}) are different, and second removing the rows 1,2,3 (whose entries are equal to the rows 4,5,6, respectively):

    (
    [ 1+√(3) 1-√(3)      0      0     -2      1      0     -2      1; 1+√(3) 1-√(3)      0      0    -2z      z      0 -2z^-1   z^-1; 1+√(3) 1-√(3)      0      0  -2z^2    z^2      0 -2z^-2   z^-2;      1      1      1     -1      1      1      1      1      1;      1      1      1     -z      z      z   z^-1   z^-1   z^-1;      1      1      1   -z^2    z^2    z^2   z^-2   z^-2   z^-2;      1      1     -1      1      1      1     -1      1      1;      1      1     -1      z      z      z  -z^-1   z^-1   z^-1;      1      1     -1    z^2    z^2    z^2  -z^-2   z^-2   z^-2 ]).







§ CONCLUDING REMARKS



In Section <ref> we presented a method for determination of a complete spectrum of a factored lift from the spectrum of a special matrix reflecting structure of a base graph together with a combined voltage assignment in a group, with entries in a complex group algebra associated with the voltage group. For a similar derivation of eigenvectors of the lift, we derived a sufficient condition, and in Section <ref>, we illustrated the complexity of the situation with lifting eigenvectors in general.

In a way, this is a bit of a paradox when one considers the previous work <cit.> of the same set of authors. The two papers offer a complete description of permutation lifts of both spectra and eigenspaces, together with details of the underpinning theory in <cit.>. While permutation lifts represent a generalization of ordinary lifts in a completely different direction compared with factored lifts (as explained in Section <ref>), it still feels like a paradox that our methods enable a complete description of lifts of spectra but not lifts of all the eigenspaces. A complete determination of the latter remains open. 

The factored lifts of base graphs equipped with a combined voltage assignment in a given group, considered in this paper, are an equivalent way of studying the quotients of graphs that admit a free action of a given group on arcs. As alluded to earlier, an investigation of quotients of graphs by general subgroups of automorphisms and a formal study of their reconstruction by `general lifts' was set out by Potočnik and Toledo in <cit.>. The question of determination of spectra and eigenspaces in such a completely general setting is also open. 






 §.§ Acknowledgment

The first two authors' research has been supported by
AGAUR from the Catalan Government under project 2021SGR00434 and MICINN from the Spanish Government under project PID2020-115442RB-I00.
The second author's research was also supported by a grant from the Universitat Politècnica de Catalunya, with references AGRUPS-2022 and AGRUPS-2023. The third and fourth authors acknowledge support of this research from the APVV Research Grants 19-0308 and 22-0005 and the VEGA Research Grants 1/0567/22 and 1/0069/23.



xx

agrr07
K. Audenaert, C. Godsil, G. Royle, and T. Rudolph,
Symmetric squares of graphs,
J. Combin. Theory B 97 (2007) 74–90.
















dfmr17
C. Dalfó, M. A. Fiol, M. Miller, and J. Ryan, On quotient digraphs and voltage digraphs, Australasian J. Combin. 69 (2017), no. 3, 368–374.

dfmrs19
C. Dalfó, M. A. Fiol, M. Miller, J. Ryan, and J. Širáň,
An algebraic approach to lifts of digraphs,
Discrete Appl. Math. 269 (2019) 68–76.

dfps21
C. Dalfó, M. A. Fiol, S. Pavlíková and J. Širáň, Spectra and eigenspaces of arbitrary lifts of graphs, J. Algebraic Combin. 54 (2021) 651–672.

dfps23
C. Dalfó, M. A. Fiol, S. Pavlíková, and J. Širáň,
On the spectra and eigenspaces of the universal adjacency matrices of arbitrary lifts of graphs,
Linear Multilinear Algebra 71(5) (2023) 693–710.

dfs19
C. Dalfó, M. A. Fiol, and J. Širáň,
The spectra of lifted digraphs,
J. Algebraic Combin. 50 (2019)
419–426.

ffhhuw12
R. Fabila-Monroy, D. Flores-Peñaloza, C. Huemer, F. Hurtado, J. Urrutia, and D. R. Wood,
Token graphs,
Graphs Combin. 28 (2012), no. 3, 365–380.

g99
H. W. Gould, The Girard-Waring power sum formulas for symmetric functions and Fibonacci
sequences Fibonacci Quart. 37 (1999), no. 2, 135–140.

gt87
J. L. Gross and T. W. Tucker,
Topological Graph Theory,
Wiley, New York (1987).






pt21
P. Potocnik and M. Toledo,
Generalised voltage graphs,
European J. Combin. 94 (2021) 103313.

rdfm23
M. A. Reyes, C. Dalfó, M. A. Fiol, and A. Messegué,
On the spectra of token graphs of cycles and other graphs,
Linear Algebra Appl. 679 (2023) 38–66.



