Edge-transitive token graphs as covers
Sergio G. Gómez-Galicia, Octavio B. Zapata-Fonseca · 2025
Read Edge-transitive token graphs as covers by Sergio G. Gómez-Galicia, Octavio B. Zapata-Fonseca (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-20632.txt.
Introduction
Sergio Gomez-Galicia and Octavio Zapata-Fonseca use covering graph theory to sort which highly symmetric graphs can arise as token graphs in a 2025 paper. A token graph tracks sets of tokens placed on a base graph, with moves that slide one token along an edge. Symmetry where every edge plays the same role narrows the field sharply. Covers, larger graphs that fold evenly onto smaller ones, give the pair a lever to classify the possibilities. The result is a clean structural picture of an appealing graph family.
Catalog record
| CREATOR | Sergio G. Gómez-Galicia, Octavio B. Zapata-Fonseca |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 13 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-20632
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Edge-transitive token graphs as covers Sergio G. Gómez-Galicia, Octavio B. Zapata-Fonseca Abstract This paper uses the theory of covering graphs to characterize some of the edge-transitive graphs which can arise as token graphs. 1 Introduction All the edge-transitive graphs which can arise as token graphs have been classified by Zhang and Zhou in [ 16 ] . The aim of the present paper is to characterize some of these edge-transitive token graphs as covering graphs. Before stating our main result precisely, Theorem 3.1 , we will discuss the background to this result in both finite group theory and topological graph theory. The graphs we consider will be directed or undirected, with or without loops, and with or without multiple edges. We will be specific. An automorphism of a finite graph X is a permutation of the vertex set V(X) that preserves all the pairs of vertices belonging to the edges E(X) . These permutations of V(X) form a group under composition, called the automorphism group of X , denoted by \Aut(X) . For the complete graph K_{n} on n vertices, \Aut(K_{n}) is isomorphic to the symmetric group S_{n} of degree n . If K_{m,n} is the complete bipartite graph with m independent vertices of degree n and n independent vertices of degree m , then \Aut(K_{m,n}) is isomorphic to the Cartesian product S_{m}\times S_{n} when m\neq n , and to the semidirect product S_{n}^{2}\rtimes\mathbb{Z}_{2} when m=n . A graph X is said to be edge-transitive if the action of \Aut(X) on E(X) has a single orbit. Such a graph may or may not be vertex-transitive. For example, the complete graph K_{n} is vertex-transitive and edge-transitive. The complete bipartite graph K_{m,n} is edge-transitive, and it is vertex-transitive only when m=n . Assuming that X is a simple undirected graph without isolated vertices (i.e., all the vertices of X have degree greater than one), if X is edge-transitive but not vertex-transitive, then the action of \Aut(X) on V(X) has exactly two orbits. These two orbits form a bipartition of X (see, e.g. [ 11 , Lemma 3.2.1] ), and so all graphs that are edge-transitive but not vertex-transitive are bipartite. A bipartite graph such that all the vertices in the same part of the bipartition have the same degree is called biregular . Every regular bipartite graph is biregular. The edge-transitive graphs which are not vertex-transitive are biregular. In this paper, we study certain edge-transitive biregular graphs which are not complete bipartite. Specifically, we study the edge-transitive graphs that arise from a construction known as the token graph. Let X be a finite, undirected, and simple graph with n vertices, and let 1\leq k\leq n-1 be an integer. The k -token graph F_{k}(X) of X is the graph with the set of all k -subsets of V(X) as vertex set, where two vertices are adjacent when their symmetric difference is an edge of X . Token graphs were introduced by Fabila-Monroy, Flores-Peñaloza, Huemer, Hurtado, Urrutia, and Wood [ 8 ] . However, these graphs have been independently introduced several times under different names. See, e.g., [ 14 , 1 , 2 ] . It is easy to see that F_{k}(X)\cong F_{n-k}(X) . Therefore we always assume 1\leq k\leq n/2 . Moreover, throughout the rest of the paper, we assume V(X)=\{1,\dots,n\} . Thus, |V(F_{k}(X))|=\binom{n}{k}. The k -token graph F_{k}(K_{n}) of the complete graph K_{n} is isomorphic to the Johnson graph J(n,k) , defined as the graph with vertex set all the k element subsets of a set with n elements, where two vertices of J(n,k) are adjacent whenever they intersect in exactly k-1 elements. Johnson graphs are examples of graphs with a vertex-transitive and edge-transitive group of automorphisms which are not complete. As we mentioned before, our intention is to characterize all the edge-transitive token graphs from the following classification [ 16 , Theorem 1.2] . Theorem 1.1 ( [ 16 ] ) . Let X be a connected graph. The token graph F_{k}(X) is edge-transitive if and only if one of the following holds: (1) X\cong K_{n} and 2\leq k\leq n-1 ; (2) X\cong K_{1,n} and 2\leq k\leq n ; (3) X\cong K_{2,n} and k=(n+2)/2 ; (4) X\cong K_{n,n} and k=2 or k=2(n-1) . We note that the family of edge-transitive token graphs F_{k}(K_{1,n}) contains concrete examples of edge-transitive biregular graphs. For instance, the token graphs F_{k}(K_{1,n}) for n odd are the doubled Johnson graphs, and the token graphs F_{2}(K_{1,n}) are the barycentric subdivisions of the complete graphs K_{n} . 2 Combined base graphs Edge-transitive biregular graphs have been extensively studied by the theory of covering graphs. We now introduce the notion of combined base graphs, and give a way to construct covering graphs above them. For edge-transitive biregular graphs, this construction was first studied under the name graph of the completion of an amalgam in [ 12 ] . It has also been studied under the names coset graph in [ 9 ] , double coset graph in [ 7 ] , and generalized cover graph in [ 15 ] . Covering graphs are defined in many texts, see e.g., [ 3 , 11 , 13 , 17 ] . Let G be a group, and let H<G be a subgroup. The set of right cosets of H in G is denoted by G/H , and the index of H in G is denoted by [G:H] . A combined voltage assignment on X in a group G is a pair of functions (\alpha,\omega) , where \alpha is a voltage assignment \alpha:E(X)\to G , and \omega is a map that sends each vertex x\in V(X) to a subgroup \omega(x)<G . The graph X is called a combined base graph if it is equipped with the combined voltage assignment (\alpha,\omega) for some group G . The covering graph X^{(\alpha,\omega)} of the combined base graph X with respect to the group G is the graph with vertex set V^{(\alpha,\omega)}:=\{(x,K)\mid x\in V(X)\text{ and }K\in G/\omega(x)\}, and the edges of X^{(\alpha,\omega)} defined as follows: for each edge xy\in E(X) with an assigned voltage \alpha(xy)\in G , there is an edge in the covering graph X^{(\alpha,\omega)} from a vertex (x,K) , for some K\in G/\omega(x) , to a vertex (y,H) , for some H\in G/\omega(y) if and only if K\alpha(xy)\cap H\neq\emptyset . If \omega maps each vertex x\in V(X) to the trivial group \{0\} , then \omega is the trivial map 0 , the base graph X is the so-called voltage graph , and the covering graph X^{(\alpha,0)} is called the covering lift (sometimes called derived graph) of the voltage graph X . 3 The token graph F_{2}({K_{n}}) as a covering graph There are several graphs that can be obtained as covering graphs of combined base graphs. For example, it is well known that Cayley graphs can be obtained as covers of base graphs with a single vertex incident with multiple loops (see [ 13 ] ). Another interesting example is the line graph L(K_{n}) of the complete graph K_{n} , also known as the triangular graph T(n) . This graph is a strongly regular graph with parameters (\binom{n}{2},2(n-2),n-2,4) if n\geq 4 . For m=5 it is the complement of the Petersen graph. There is an isomorphism