On the Problem of Determining which (n, k)-Star Graphs are Cayley Graphs

Abstract

In this paper we work to classify which of the (n, k)-star graphs, denoted by $S_{n,k}$, are Cayley graphs. Although the complete classification is left open, we derive infinite and non-trivial classes of both Cayley and non-Cayley graphs. We give a complete classification of the case when $k=2$, showing that $S_{n,2}$ is Cayley if and only if n is a prime power. We also give a sufficient condition for $S_{n,3}$ to be Cayley and study other structural properties, such as demonstrating that $S_{n,k}$ always has a uniform shortest path routing.

1 Introduction

In the design of parallel computing machines, the first step is to decide how processors are linked. A static interconnection network has processor-to-processor communication links among the processors. For example, they can be used for message-passing architectures. (See [24] for details.) The underlying graph topology is the corresponding interconnection network. The class of n-cubes (or hypercubes) was the first major class of interconnection networks. The star graph proposed by Chiang and Chen [11] has many advantages over the n-cube such as lower degree and smaller diameter. Different aspects of star graphs and related interconnection networks are studied extensively, including topological issues [20, 30, 34, 38], broadcasting issues [27, 29, 35], routing issues when faults are present [14, 16, 17], and many other additional topics [3, 4, 7, 25, 26]. Star graphs are governed by one parameter. The star graph $S_n$ has n! vertices and it is an $(n-1)$-regular graph. The n-cube, on the other hand, is an n-regular graph on $2^n$ vertices. Although star graphs are better than n-cubes in many aspects, they do suffer from a scaling problem as the gap between two consecutive factorials is large. For this reason, two generalizations were developed, one of which is the class of (n, k)-star graphs [11]. An (n, k)-star graph $S_{n,k}$ is governed by two parameters n and k, where $1\le k < n$. Moreover, $S_{n,k}$ is an $(n-1)$-regular graph on $n!/(n-k)!$ vertices; in particular, $S_{n,n-1}$ is isomorphic to the star graph $S_n$.

The star graph $S_n$ is so named due to its generating graph being the star $K_{1,n-1}$. Given the star $K_{1,n-1}$, we label the vertices using the symbols $1,2,\ldots ,n$ with 1 being the center of the star. The graph $S_n$ consists of n! vertices, labeled by the permutations on n symbols, usually $1,2,\ldots ,n$. Two vertices of $S_n$ are adjacent if one permutation can be obtained from the other by exchanging the symbols in position 1 and position i for some $2\le i\le n$. (Here $1,2,3,\ldots ,n$ are used as position numbers as well as symbols in permutations.) Note that $(1,i)$ for $2\le i\le n$ are precisely the edges in our labeled $K_{1,n-1}$. Hence in a sense $K_{1,n-1}$ generates $S_n$ and thus it is called the star graph, although a more proper term would be the star-generated graph.

The (n, k)-star graph $S_{n,k}$, where $1\le k < n$, has all k-permutations on the ground set $\{1,2,\ldots ,n\}$ as its vertices. (A k-permutation on $\{1,2,\ldots ,n\}$ is an ordered k-tuple obtained by first choosing k symbols from this set and then permuting the symbols.) There are two types of edges in $S_{n,k}$. A star edge is an edge between two vertices where one k-permutation can be obtained from the other by exchanging the symbols in position 1 and position i for some $2\le i\le k$. A residual edge is an edge between two vertices where one k-permutation can be obtained from the other by replacing the symbol in position 1 by a symbol not in the k-permutation. Clearly a vertex in $S_{n,k}$ is incident to $k-1$ star edges and $n-k$ residual edges. It is also clear that $S_{n,n-1}$ is isomorphic to $S_n$. Moreover, $S_{n,1}$ is the complete graph on n vertices, $K_n$. Since (n, k)-star graphs were introduced to address shortcomings of star graphs, they have been studied extensively in a wide range of topics [2, 6, 10, 13, 21, 31, 36, 37, 39].

Interconnection networks usually have parameters in which the number of vertices is exponential or even combinatorial (that is, expressions involving factorials) with respect to these parameters. One basic task is to find good shortest path routing algorithms. However, the restriction here is that the running time has to be polynomial with respect to these parameters and not the number of vertices. Moreover, such algorithms need to be distributive in nature. So to route from a source to a sink, at every step, one can only use the information of the source, the sink and the current vertex (or information of all the vertices at a fixed distance from the current vertex) to determine the next step. This is impossible unless local information yields global information. In other words, interconnection networks should have symmetry. This naturally leads to using Cayley graphs as interconnection networks.

Let G be a finite group and S be a set of elements of G such that the identity of the group does not belong to S. The Cayley graph $\overrightarrow{\Gamma }(G,S)$ is the directed graph whose vertex set is G, and there is an arc from u to v if and only if there is an $s\in S$ such that $v=us$. If $s\in S$ if and only if $s^{-1}\in S$, then there is an arc from u to v if and only if there is an arc from v to u, so $\overrightarrow{\Gamma }(G,S)$ can be simplified to be an undirected graph by replacing each such pair of arcs with an undirected edge; in this paper we will assume that this is always the case and denote the resulting undirected graph $\Gamma (G,S)$.

Clearly if S is a generating set for G the graph $\Gamma (G,S)$ is connected, henceforth we will assume that S is a generating set for G. We note that $\Gamma (G,S)$ is regular, say with regularity r, and it is known that it has edge connectivity r, but its vertex connectivity may be low. The star graph $S_n$ is a well known Cayley graph in which G is the symmetric group on $\{1,2,\ldots ,n\}$, and S consists of the transpositions of the form $(1,i)$ for all $2\le i\le n$ (note, as is the case with all graphs considered in this paper, $s\in S$ if and only if $s^{-1}\in S$ and S generates the symmetric group on $\{1,2,\ldots ,n\}$). Note that these $(1,i)$’s correspond precisely to the edges of $K_{1,n-1}$ that we have considered. Indeed, another generalization of $S_n$ is to replace $K_{1,n-1}$ by a tree on n vertices and consider the edges of this tree as transpositions. This is the class of Cayley graphs generated by transposition trees [1, 5, 33]. It is worth noting that from pure combinatorics, one can study factorizations of permutations into transpositions of special forms that are related to star graphs or “factorization” of k-permutations [2, 22].

Although many classes of interconnection networks such as n-cubes, star graphs, meshes and tori are Cayley graphs, it has remained an unanswered question whether the (n, k)-star graphs are Cayley graphs. In fact, to the best of our knowledge, this work is the first progress on this problem, beyond the cases when $k=n-1$, where the (n, k)-star graph is isomorphic to the star graph, when $k=1$, where the (n, k)-star graph is the complete graph on n vertices, and the case when $k=n-2$. In this paper, we give a complete classification of when $S_{n,2}$ is a Cayley graph as well as partial results for $S_{n,3}$. Moreover, we give evidence of why this problem is difficult.

To the best of our knowledge, no efficient way of determining whether or not a graph is Cayley is known (although, we are also not aware of any proofs of hardness of this problem). Additionally, the number of vertices in $S_{n,k}$ is $n \atopwithdelims ()k$ and thus, even if an algorithm to test if a graph was a Cayley graph was known that ran in time polynomial in the number of vertices and edges of the graph, its running time would still be intractable with respect to the parameter n. One technique to check if a graph is Cayley is to apply Sabidussi’s Theorem [28], which requires computation of the automorphism group of the graph. One necessary condition for a graph to be Cayley is that it admits a uniform shortest path routing, therefore if it can be shown that a given graph does not have a uniform shortest path routing, this allows one to conclude that the graph is not Cayley. It was once conjectured that existence of a uniform shortest path routing was a necessary and sufficient condition for a graph to be Cayley, but this was later shown to be false. In Sect. 2, we show that $S_{n,k}$ always has a uniform shortest path routing, which is an indication of why the the corresponding classification problem is difficult, i.e. that $S_{n,k}$ exhibits some “Cayley-like” properties. In Sect. 3, we give the classification for $S_{n,2}$, together with partial results for $S_{n,3}$, and we give concluding remarks in Sect. 4.

2 Structural Properties of $S_{n,k}$

2.1 Uniform Shortest Path Routings

A routing in a graph $G = (V,E)$ is a set of paths $R = \{P_{uv} \mid (u, v) \in V \times V, u \ne v\}$ where each path $P_{uv}$ starts at u and ends at v. A good routing should not load any vertex too much, in the sense that not too many paths specified by the routing should go through it. In order to measure the load of a vertex, Chung et al. [12] proposed the notion of the forwarding index. The vertex-forwarding index of G with respect to R is defined as the maximum number of paths in R passing through any vertex of G. The vertex-forwarding index of G, denoted by $\xi (G)$, is defined as the minimum vertex forwarding index of G with respect to R over all routings R of G.

A routing R is a shortest path routing if each path $P_{uv}$ in R is a shortest u to v path. A shortest path routing is uniform if every node $w \in V$ appears as an internal vertex in exactly the same number of paths in R. In other words, if $l_R(u)$ denotes the number of paths in R in which u appears as an internal vertex, then in a uniform shortest path routing $l_R(u)$ must be the same for every $u \in V$. The following result bounds the vertex-forwarding index of a graph.

Theorem 1

(Chung et al. [12]) Let G be a connected graph of order n and let $d_G(u,v)$ denote the distance between vertices u and v in G. Then

$$\begin{aligned} \frac{1}{n} \sum _u \sum _{v\ne u} \big (d_G(u,v)-1\big )\le \xi (G)\le (n-1)(n-2), \end{aligned}$$

and the lower bound is achieved if and only if there exists a uniform shortest path routing in G. The graph that attains this upper bound is the star $K_{1,n}$.

It is well known that all connected Cayley graphs have uniform shortest path routings [19]. Therefore, since many of the well known interconnection networks are Cayley graphs, including the star graph $S_n$ and the n-cube $Q_n$, they have uniform shortest path routings. In fact, it was conjectured that all vertex-transitive graphs contained uniform shortest path routings until a counterexample was given in 2002 in [32]. In this section we show that $S_{n,k}$ always has a uniform shortest path routing, demonstrating that it has a nice “Cayley-like” property. This also means that it will not be possible to show any graphs in this class to be non-Cayley by attempting to show the absence of uniform shortest path routings.

Algorithms to construct shortest paths in $S_{n,k}$ are well known; the original paper defining star graphs [11] defines a greedy shortest path algorithm. Although the description in the original paper gives more freedom of choice in the order of the moves, stated in terms of correcting internal and external cycles, we restate the algorithm in a slightly different format to enforce a precise ordering of the swaps. For justification of the correctness of this algorithm, and an example of its application, see [11]. Our algorithm follows the same pattern and uses a lexicographical tie-breaking rule in case multiple greedy choices are possible. The algorithm will take a k-permutation on n symbols $u = [u_1,u_2,\ldots ,u_k]$ and repeatedly swap the first symbol with one of the other $k-1$ symbols until a target vertex $v=[v_1,v_2,\ldots ,v_k]$ is reached.

Note that given u and v, this algorithm unambiguously produces a shortest $u\,$–$\,v$ path; we call any path produced by the algorithm a canonical shortest path. We make the important observation that the algorithm depends in no way on what the actual labels of the symbols in the k-permutations are but only on their relative positions. We now come to our first new result, establishing the existence of uniform shortest path routings in (n, k)-star graphs.

Theorem 2

For any $n\ge k\ge 2$, the graph $S_{n,k}$ has a uniform shortest path routing.

Proof

We show that the set of canonical shortest paths is a uniform shortest path routing. First, let $V=V(S_{n,k})$ and assign

$$\begin{aligned} R=&\{P_{uv}\mid (u,v)\in V\times V,u\ne v, P_{uv}\text { is the canonical } \\&\quad \text {shortest path from }u \text { to }v\text { in }S_{n,k}\}. \end{aligned}$$

By construction, R is a shortest path routing; we are left to show that the routing is uniform. For $u\in V$, let $R_u$ be the set of paths in R that contain u as an internal vertex. Let $x,y\in V$, and we show that $|R_x|=|R_y|$ by constructing a bijection between $R_x$ and $R_y$; this demonstrates that the load on each vertex is identical.

Let $\pi :\{1,\ldots ,n\}\rightarrow \{1,\ldots ,n\}$ be a permutation on n symbols that maps x to y, i.e., if we replace each number in x with its image under $\pi$, we get y. Note that there may be many choices for $\pi$. The permutation $\pi$ induces a map $\sigma _\pi :V\rightarrow V$ defined the same way: for any vertex $v\in V$, replace each number in v by its image under $\pi$, and the resulting k-permutation is $\sigma _\pi (v)$. It is easy to see that for $u,v\in V$, the vertex $\sigma _\pi (u)$ is connected to $\sigma _\pi (v)$ by a star edge or residual edge in $S_{n,k}$ if and only if the same type of edge connects u and v in $S_{n,k}$. Therefore $\sigma _\pi$ gives an automorphism on $S_{n,k}$. Letting P be the set of all paths in $S_{n,k}$ we define $f:P\rightarrow P$ as follows: for $p=(p_1,p_2,\ldots , p_m)\in P$ we let $f(p):=p'=(p_1',p_2',\ldots , p_m')=(\sigma _\pi (p_1),\sigma _\pi (p_2),\ldots ,\sigma _\pi (p_m))$. Note that since $\sigma _\pi$ is an automorphism, we are guaranteed that $f(p)\in P$, moreover, f must also be a bijection from P to P.

Now suppose that $p\in R_x$, meaning that $p=(p_1,p_2,\ldots , p_m)$ is the canonical shortest path from $p_1\in V$ to $p_m\in V$, with $x=p_l$ for some $1<l<m$. Considering f(p), we see that $y=p_l'$ and is thus an internal vertex on that path. Moreover, since $\sigma _\pi$ has only replaced the symbols in $p_1$ and $p_m$, the routing algorithm applied to $p_1'$ and $p_m'$ would produce precisely $p'$. This means that $p'$ is the canonical shortest path from $p_1'$ to $p_m'$ and $p'\in R_y$. Since f is a bijection from P to P, we have that the restriction of f to $R_x$ is an injection from $R_x$ to $R_y$, and by a similar argument we can see that the restriction of $f^{-1}$ to $R_y$ gives an injection from $R_y$ to $R_x$. Thus the restriction of f to $R_x$ is a bijection from $R_x$ to $R_y$, thus $|R_x|=|R_y|$. $\square$

We remark that there are many other definitions for canonical shortest paths that would enable the same proof to work for Theorem 2. In particular, it is only necessary that the shortest path algorithm computes a path from u to v in a way that chooses the path based only on the relative positions of symbols in the k-permutations u and v and not on the actual values or ordering of those symbols.

Corollary 1

For any $n\ge k\ge 2$ we have

$$\begin{aligned} \xi (S_{n,k})=\frac{1}{n} \sum _u \sum _{v\ne u}\big (d_{S_{n,k}}(u,v)-1\big ). \end{aligned}$$

We remark that the lower bound given in Theorem 1 is a simple adjustment of the average distance of G. A related concept called the surface area is defined as follows: Given a vertex v and an integer d, the surface area of G with radius r at v is the number of vertices of distance d from v. It now follows from the generating function of the surface area of $S_{n,k}$ [8] that a closed form formula of $\xi (S_{n,k})$ can be found. (Although the generating function is complicated, a nicer formula for the average distance can be found.)

Analogous to the vertex-forwarding index, Heydemann et al. [19] have defined the edge-forwarding index of G with respect to a routing R to be the maximum number of paths in R passing through any edge in G. The edge-forwarding index of a graph G, denoted $\pi (G)$, is the minimum edge-forwarding index over all routings R in G. Similar to Theorem 1, it was shown in [19] that

$$\begin{aligned} \frac{1}{|E|} \sum _u \sum _{v\ne u} d_G(u,v)\le \pi (G). \end{aligned}$$

Since the equality in this bound holds if and only if G admits a shortest path routing in which every edge has equal load, we call such a routing an edge-uniform shortest path routing. Gauyacq [15] has studied the edge-forwarding index of star graphs and other Cayley graphs, and it is known that some, but not all, Cayley graphs admit edge-uniform shortest path routings. In the following remark we note that the (n, k)-star graph need not have edge-uniform shortest path routings.

Remark 1

Using a computer check we have computed that if $G=S_{4,2}$ we have:

$$\begin{aligned} \frac{1}{|E(G)|} \sum _u \sum _{v\ne u} d_G(u,v)= 15 \quad \text { and } \quad \pi (G)= 18. \end{aligned}$$

In the above remark, the value of $\pi (S_{4,2})$ was calculated by solving an integer programming formulation of a multi-commodity flow model where feasible solutions encoded routings and the objective function minimized the maximum edge load of the routing. Although we have not pursued this question further, we would conjecture that most (n, k)-star graphs do not admit edge-uniform shortest path routings.

2.2 The Structure of $S_{n,2}$ and $S_{n,3}$

The following propositions provide an alternative definition of $S_{n,2}$ and $S_{n,3}$ in terms of their structure. These representations provide a convenient way to identify them later on.

Proposition 1

Let $G=(V,E)$ be an $(n-1)$-regular graph with $n(n-1)$ vertices. Suppose that V can be partitioned into n sets of size $n-1$, labeled $H_1,\ldots ,H_n$, such that the subgraph of G induced by the vertices in $H_i$ is complete, moreover, for any distinct i, j, there is exactly one pair of vertices u, v such that u is in $H_i$, v is in $H_j$ and $(u,v)\in E$. Then G is isomorphic to $S_{n,2}$.

Proof

Suppose that G satisfies the above conditions. We will show how to label each vertex of G with a 2-permutation, giving the isomorphism between G and $S_{n,2}$. Consider a vertex v belonging to a partite set $H_j$. Since v has degree $(n-1)$, it must have exactly $n-2$ neighbors in $H_j$ and a single outgoing edge whose other end is in another partite set $H_i$ with $i\ne j$. For each v we assign it the label $[i,j]$ according to these two partite sets. Note that of the $n(n-1)$ possible 2-permutations on $1,\ldots ,n$, each appears exactly once since we have assumed that there is a unique edge between any two of the partite sets.

Finally, we will show that for any pair of nodes u, v, there is an edge between them in G if and only if their corresponding labels correspond to nodes connected in $S_{n,2}$. Edges in $S_{n,2}$ may come in only two forms. First, we have an edge between $[i,j]$ and $[k,j]$ for $i\ne k$, and the nodes in G with these labels must also be connected as they both appear in the same partite set $H_j$, which induces a complete subgraph. The second type of edge in $S_{n,2}$ will be between nodes with labels $[i,j]$ and $[j,i]$ for some $i\ne j$. By the definition of the labeling, this edge also appears in G and corresponds to the unique edge between partite sets $H_i$ and $H_j$. Since all edges in G fall into one of these two categories, the edges in G are in direct correspondence with the edges of $S_{n,2}$ and the graphs are isomorphic. $\square$

Given a graph G, an edge in G is called a star-like edge if it is not in a 3-cycle, otherwise it is called a residual-like edge. A 6-cycle is called a star-like 6-cycle if it contains solely star-like edges. This definition is motivated by the fact that in $S_{n,3}$ ($n\ge 5$) a star-like edge is a star edge, and a residual-like edge is a residual edge.

Proposition 2

Let $n\ge 5$ and $G=(V,E)$ be an $(n-1)$-regular graph with $n(n-1)(n-2)$ vertices. Suppose that

• (i) V can be partitioned into n sets of size $(n-1)(n-2)$, labeled $H_1,\ldots ,H_n$, such that the subgraph of G induced by the vertices in $H_i$ is isomorphic to $S_{n-1,2}$ for each i;

• (ii) for any ordered triple $(H_i,H_j,H_k)$ with distinct i, j, k, there is a unique 6-tuple of vertices $(v_{kji},v_{jki},v_{ikj},v_{kij},v_{jik},v_{ijk})$ with the first two vertices in $H_i$, the middle two in $H_j$, the last two in $H_k$, and these six vertices form a star-like 6-cycle in that order;

• (iii) for any distinct $1\le i,j,k,\ell \le n$, vertices $v_{kji}$ and $v_{\ell ji}$ are joined by a residual-like edge. Then G is isomorphic to $S_{n,3}$.

Proof

First we check that $S_{n,3}$ satisfies the above conditions. Let $H_i$ be the set of vertices of the form $[j,k,i]$ with i fixed. Then we can relabel this vertex in $H_i$ by $[j,k]$ for each $j,k\in \{1,\dots ,n\}{\setminus }\{i\}$. In this relabeling the vertices $[j,k]$ and $[j',k]$ are adjacent whenever $j\ne j'$, and $[j,k]$ and $[k,j]$ are also adjacent whenever $j\ne k$. Thus $H_i$ is isomorphic to $S_{n-1,2}$. Moreover, to show the existence of the 6-tuple, choose $v_{abc}=[a,b,c]$ whenever a, b, c are distinct. The uniqueness of the 6-tuple is easy to see. It is also clear that this 6-cycle is star-like. Moreover it is easy to see that condition (iii) is satisfied.

Now assume that G satisfies the given conditions. Since each $H_i$ is isomorphic to $S_{n-1,2}$, each vertex is incident to at least $n-3$ residual-like edges within the $H_i$ containing it. Graph G is ($n-1$)-regular, so each vertex has two more incident edges, one within the $H_i$, one going outside. Thus each vertex can be part of at most one star-like 6-cycle, so by property (ii), each has to be part of exactly one. So the other two edges incident to each vertex must be star-like edges, and the labellings in (ii) assign a unique label to each vertex. Label vertex $v_{ijk}$ with $[i,j,k]$ for every distinct i, j, k. In this labeling, vertex $[k,j,i]$ is adjacent to $[j,k,i]$ and $[i,j,k]$, as well as to $[\ell ,j,i]$ for every $\ell \ne i,j,k$ by (iii). So this labeling gives an isomorphism between G and $S_{n,3}$. $\square$

3 Cayley Classification

As a first step in determining which of $S_{n,k}$ are Cayley graphs, we consulted catalogs of Cayley graphs of small size such as http://staffhome.ecm.uwa.edu.au/~00013890/remote/cayley/index.html. This page lists all Cayley graphs with up to 31 vertices, organized by their groups. Although $S_{n,k}$ only falls within this size for some very small values of n and k, we note that this catalog provided helpful insight. In particular, it confirmed that $S_{6,2}$ is not Cayley and that $S_{5,2}$ is Cayley and generated from the group $\text {Hol}(C_5)$.

3.1 Cayley (n, k)-Star Graphs

It is well known that $S_{n,n-1}$ is isomorphic to the star graph $S_n$ (see [11]); an isomorphism from $S_n$ to $S_{n,n-1}$ can be constructed by mapping each permutation to the $(n-1)$-permutation formed by truncating the last symbol. The first proposition here follows directly from the fact that $S_{n,n-1}$ is isomorphic to the star graph $S_n$, which is a Cayley graph for all values of n.

Proposition 3

$S_{n,n-1}$ is a Cayley graph for all $n\ge 2$.

An obvious next step is to see whether $S_{n,n-2}$ is Cayley. Indeed, it is known that such a graph is Cayley. We will simply attribute this as a folklore result. As an interesting side note, recently researchers introduced a “new” class of interconnection networks called the alternating group networks [23], and [40] gave a proof that these networks are Cayley. However, [9] showed that these graphs are isomorphic to $S_{n,n-2}$. For completeness, we will include a proof here. Here we use the alternating group $A_n$, the subgroup of the symmetric group made up of the even permutations.

Proposition 4

$S_{n,n-2}$ is a Cayley graph for $n\ge 3$.

Proof

Consider the Cayley graph $G = \Gamma (A_n,S)$ where the set of generators S is taken to be $S=\{(1,2)(n-1,n),(1,3)(n-1,n)\ldots ,(1,n-2)(n-1,n), (1,n-1,n),(1,n,n-1)\}$. These generators are of two types. The first type will swap the first symbol with any of the symbols in positions 2 up to $n-2$ and also swap the symbols in positions $n-1$ and n. The second type are the 3-cycles that rotate the first symbol with the symbols in position $n-1$ and n.

We now construct an isomorphism f from G to $S_{n,n-2}$. Let $p=[p_1,p_2,\ldots ,p_n]$ be a permutation in $A_n$, we map p to the $(n-2)$-permutation on n elements by $f(p)=[p_1,p_2,\ldots ,p_{n-2}]$. Note that f is a bijection from $A_n$ to the $(n-2)$-permutations since an $(n-2)$-permutation can be extended to an even permutation on n elements in a unique way (there are only two choices for how to append the remaining symbols; one results in an even permutation, and the other one results in an odd permutation). Moreover, to see that f gives an isomorphism, we observe that the generators in S correspond to precisely the edges in $S_{n,n-2}$, that is, the edges corresponding to swapping the first symbol in the $(n-2)$-permutation with any of the other symbols present in another position, or exchanging it with one of the symbols not appearing. $\square$

One conceivable approach for showing that some additional (n, k)-star graphs are Cayley graphs would be to generate Cayley graphs of various subgroups of the symmetric group and then map the vertices of these Cayley graphs to the vertices of $S_{n,k}$ by truncating the permutations to be k-permutations. Although this has worked in the above two cases, we did not find an obvious way of how this approach can be carried out in other cases.

3.2 $S_{p^{m},2}$ is Cayley

Let $q=p^{m}$. Given a finite field $F_{q}$ having q elements, it is well-known [18, Theorem 5.3] that the multiplicative group $F^{*}_q$ of nonzero elements is cyclic, thus if we let $\sigma$ be a generator of $F^{*}_q$, then

$$\begin{aligned} F^{*}_q=\langle \sigma \rangle =\{1,\sigma ,\dots ,\sigma ^{q-2}\}\cong C_{q-1}. \end{aligned}$$

Define the semidirect product

$$\begin{aligned} F_q\rtimes F^{*}_q=\{(a,b)\mid a\in F_q,\; b\in F^{*}_q\}, \end{aligned}$$

(1)

where the group operation is given by $(a,b)(a',b')=(a+ba',bb')$. Note that $F_q\rtimes F^{*}_q$ has $q(q-1)$ elements. We also give an equivalent definition. Recall that the general linear group and the projective general linear group are defined as follows:

$$\begin{aligned} \mathrm{GL}(2,q):=&\bigg \{ \begin{bmatrix} a&\quad b \\ c&\quad d \end{bmatrix}\in M_2(F_q) \;\bigg |\; ad-bc\ne 0 \bigg \},\\ \mathrm{PGL}(2,q):=&\mathrm{GL}(2,q) \bigg / \bigg \{\begin{bmatrix} a&\quad 0\\ 0&\quad a \end{bmatrix}\in M_2(F_q) \;\bigg |\; a\ne 0 \bigg \}. \end{aligned}$$

Then $F_q\rtimes F^{*}_q$ can be viewed as a subgroup of $\mathrm{GL}(2,q)$ and $\mathrm{PGL}(2,q)$:

$$\begin{aligned} F_q\rtimes F^{*}_q\cong \bigg \{\begin{bmatrix} b&\quad a\\ 0&\quad 1 \end{bmatrix}\in \mathrm{GL}(2,q) \bigg \} \cong \bigg \{\begin{bmatrix} b&\quad a\\ 0&\quad 1 \end{bmatrix}\in \mathrm{PGL}(2,q) \bigg \}, \end{aligned}$$

(2)

where the isomorphism is given by

$$\begin{aligned} (a,b)\mapsto \begin{bmatrix} b&\quad a\\ 0&\quad 1\\ \end{bmatrix}. \end{aligned}$$

We now introduce notation for the following elements in $F_q\rtimes F^{*}_q$:

$$\begin{aligned} 1=(0,1),\quad t=(0,\sigma ), \quad s=(1,-1), \end{aligned}$$

where $-1$ is the involution of $F^{*}_q$, that is, the unique non-identity element whose square is 1.

Lemma 1

The elements of G listed below are all distinct:

$$\begin{aligned} F_q\rtimes F^{*}_q=\{1,t,\ldots ,t^{q-2}\}\cup \{t^{i}st^{j}\mid 0\le i,j\le q-2\}. \end{aligned}$$

(3)

Moreover, $s^{2}=1$, and for each $i\not \equiv 0\pmod {q-1}$, there exist unique $j,k\not \equiv 0\pmod {q-1}$ such that

$$\begin{aligned} st^{i}st^{j}st^{k}=1. \end{aligned}$$

(4)

As a consequence, $F_q\rtimes F^{*}_q$ is generated by s and t.

Proof

We first note that $s\ne 1$ and $s^2=1$, so s has order 2.

Next we show that all the $q(q-1)$ elements listed in (3) are distinct, then because $F_q\rtimes F^{*}_q$ has exactly $q(q-1)$ elements according to (1), we conclude that (3) lists all elements. Indeed, since the order of t is $q-1$, the powers $1,t,\ldots ,t^{q-2}$ are distinct from each other. Next, an element of form $t^k$ is distinct from an element of from $t^{i}st^{j}$. Otherwise assume $t^{k}=t^{i}st^{j}$, then $(1,-1)=s=t^{k-i-j}=(0,\sigma ^{k-i-j})$, which is absurd. Furthermore, elements of the form $t^ist^j$ are distinct from each other. To see this, assume $t^{i}st^{j}=t^{k}st^{\ell }$ with $0\le i,j,k,\ell \le q-2$. Then $t^{i-k}s=st^{\ell -j}$, hence $(\sigma ^{i-k},-\sigma ^{i-k})=(1,-\sigma ^{\ell -j})$, hence $i=k$ and $j=\ell$. This completes the proof that all elements listed in (3) are distinct.

In the last statement of the lemma we rewrite (4) as $st^{-i}s=t^{j}st^{k}$. Then the existence and uniqueness of j and k follows from (3) once we show that $j,k\not \equiv 0\pmod {q-1}$. Indeed, if $j\equiv 0$, then $st^{-i}s=st^{k}$, hence $t^{-i}s=t^{k}$, which is impossible because of (3); similarly $k\equiv 0$ is impossible. $\square$

Proposition 5

Let p be a prime number, m be a positive integer. Then $S_{p^{m},2}$ is a Cayley graph.

Proof

Let $q=p^{m}$, $G=F_{q}\rtimes F^{*}_{q}$, $S=\{t,t^{2},\dots ,t^{q-2},s\}$. It follows from Lemma 1 that S generates G and $S=S^{-1}$. We claim that

$$\begin{aligned} \Gamma (G,S)\cong S_{q,2}. \end{aligned}$$

Let T be the subgroup $\langle t\rangle =\{1,t,t^{2},\dots ,t^{q-2}\}$ of G. Then $\Gamma (G,S)$ has complete subgraphs $H_1=T, H_2=sT, H_3=tsT, H_4=t^{2}sT, \dots , H_{q}=t^{q-2}sT$; all isomorphic to the complete graph $K_{q-1}$. Thanks to Lemma 1, it suffices to prove that for any distinct i, j ($1\le i<j\le q$), there is exactly one pair of elements $u\in H_i, v\in H_j$ such that $(u,v)$ is an edge in $\Gamma (G,S)$. We prove this by considering two cases:

Case 1 $i=1$. Denote $u=t^a$, $v=t^{j-2}st^{b}$ where $2 \le j\le q$. Then $(u,v)$ is an edge if and only if $v=us$ or $v=ut^c$ for some $1\le c\le q-2$. Using Lemma 1, the second equation, which is $t^{j-2}st^b=t^{a+c}$, never holds; and the first equation, which is $t^{j-2}st^b=t^as$, holds if and only if $a=j-2$ and $b=0$. Thus there is exactly one edge between $H_{1}$ and $H_{j}$.

Case 2 $i\ge 2$. We need to show that there exists a unique pair a, b ($0\le a,b\le q-2$) such that $u=t^{i}st^{a}$ and $v=t^{j}st^{b}$ are joined by an edge, that is, $v=us$ or $v=ut^{c}$ for some $1\le c\le q-2$. Using Lemma 1 and that $i<j$, the second equation never holds. The first equation is equivalent to

$$\begin{aligned} t^{i}st^{a}s=t^{j}st^{b}, \end{aligned}$$

which is equivalent to

$$\begin{aligned} st^{j-i}st^{b}st^{-a}=1. \end{aligned}$$

This equation has a unique solution of (a, b) by Lemma 1, finishing the proof. $\square$

3.3 Necessary and Sufficient Conditions for $S_{n,2}$ to be Cayley

Lemma 2

Assume $S_{n,2}\cong \Gamma (G,S)$, where $n\ge 4$. Then the following hold:

• (i) $S=(T{\setminus }\{1\})\cup \{s\}$, where T is a subgroup of G of order $n-1$, and s is an order 2 element. Moreover, $V(G)=T\cup TsT=T\cup \{tst'\mid t,t'\in T\}$, and this is a disjoint union.

• (ii) If $g\in G{\setminus } T$, then the $(n-1)$ conjugate elements $tgt^{-1}$ for $t\in T$ are all distinct and not in T.

• (iii) If $g\in G{\setminus } T$, then $T\cap gTg^{-1}=\{1\}$. In particular, T is not normal.

• (iv) There are n distinct conjugate subgroups of T in G, namely T and $tsTst^{-1}$ for each $t\in T$. The intersection of any two distinct conjugate subgroups contains only the identity.

Proof

• (i) The graph $S_{n,2}$ has the property that each vertex is incident to exactly one edge that is not in a 3-cycle. Assume that vertex 1 is joined to vertex s by such an edge e. Consider the automorphism $f:g\mapsto gs$ of $S_{n,2}$. It must send the edge e to an edge incident to s that is not in a 3-cycle, which has to be e. Thus $f(s)=1$, in other words, $s^2=1$. Since we assume $1\notin S$, s is of order 2.

  Now consider the complete subgraph $K\cong K_{n-1}$ of $S_{n,2}$ that contains 1. None of the edges between K and $S_{n,2}- K$ are in 3-cycles, so they all correspond to s. All edges inside K correspond to $S{\setminus }\{s\}$, thus $T:=(S{\setminus }\{s\})\cup \{1\}$ is closed under multiplication, therefore must be a subgroup of G.

  Next, note that the n left cosets of T correspond to the n complete subgraphs of $S_{n,2}$ isomorphic to $K_{n-1}$. By the property of $S_{n,2}$, any two cosets of T are joined by an edge, which must correspond to s because it is not in a 3-cycle. Therefore, for an arbitrary element $x=at_{2}\in aT$ such that $a\in V(G)$, $t_2\in T$, and $x\not \in T$, there exists an edge between aT and T, so there is an element $at_{1}\in aT$ and $t\in T$ such that $at_{1}=ts$. Then $x=at_{2}=(tst_{1}^{-1})t_{2}=tst'\in TsT$ where $t'=t_{1}^{-1}t_{2}$. This shows $V(G)=T\cup TsT$.

  Finally, note that $|T|=n-1$ and $|TsT|\le (n-1)^{2}$, thus

  $$\begin{aligned} n(n-1)=|S_{n,2}|=|G|\le |T|+|TsT|\le (n-1)+(n-1)^{2}=n(n-1). \end{aligned}$$

  So both inequalities must be equalities. This implies that all elements in T and $\{tst'\mid t,t'\in T\}$ are distinct from each other.

• (ii) Assume $t\ne t'$ are two elements in T such that $tgt^{-1}=t'gt'^{-1}$. By (i), there exist $t_{1},t_{2}\in T$ such that $g=t_{1}st_{2}$. Then

  $$\begin{aligned} tt_{1}st_{2}t^{-1}=t't_{1}st_{2}t'^{-1} \end{aligned}$$

  Again by Lemma 2, $tt_{1}=t't_{1}$, $t_{2}t^{-1}=t_{2}t'^{-1}$. This contradicts the assumption $t\ne t'$.

  Furthermore, if $tgt^{-1}\in T$, then $g\in t^{-1}Tt=T$, contradicting to the assumption.

• (iii) Assume $t\in T\cap gTg^{-1}$. By (i), there exist $t_{1},t_{2}\in T$ such that $g=t_{1}st_{2}$. So $t\in gTg^{-1}$ implies that there exists $t'\in T$, such that

  $$\begin{aligned} t=(t_{1}st_{2})t'(t_{1}st_{2})^{-1}. \end{aligned}$$

  Then

  $$\begin{aligned} tt_{1}st_{2}=t_{1}st_{2}t', \end{aligned}$$

  implying $tt_{1}=t_{1}$, $t_{2}=t_{2}t'$, thus $t=1$.

• (iv) If $g\in T$, then $gTg^{-1}=T$. If $g\notin T$, write $g=tst'$ with $t,t'\in T$. Then

  $$\begin{aligned} gTg^{-1}=tst'Tt'^{-1}st^{-1}=tsTst^{-1}. \end{aligned}$$

  So all conjugacy subgroups of T are listed as in (iv).

Next we show that these n conjugate subgroups are distinct. It follows from (iii) that T is distinct from the rest. If two conjugate subgroups coincide, so $t_{1}sTst_{1}^{-1}=t_{2}sTst_{2}^{-1}$, then

$$\begin{aligned} T=(st_{1}^{-1}t_{2}s)T(st_{1}^{-1}t_{2}s)^{-1}. \end{aligned}$$

By (iii),$st_{1}^{-1}t_{2}s=1$, thus $t_{1}=t_{2}$.

Now we show that the intersection of any two distinct conjugate subgroups contains only the identity. If one of these two subgroups is T, this follows from (iii). Now assume

$$\begin{aligned} t\in t_{1}sTst_{1}^{-1}\cap t_{2}sTst_{2}^{-1} \end{aligned}$$

where $t_{1}, t_{2}\in T$ and $t_{1}\ne t_{2}$. Then by (iii) and the fact that $st_1^{-1}t_2s\notin T$,

$$\begin{aligned} st_{1}^{-1}tt_{1}s\in T\cap st_{1}^{-1}t_2sTst_{2}^{-1}t_{1}s=\{1\}. \end{aligned}$$

So $st_{1}^{-1}tt_{1}s=1$, implying $t=1$. $\square$

Theorem 3

The graph $S_{n,2}$ is a Cayley graph if and only if n is a prime power.

Proof

The “if” part follows from Proposition 5.

For the “only if” part, assume the contrary that n is not a prime power. Let p, q be two distinct prime factors of n, and let $m_{p}$ and $m_{q}$ be the numbers of order p and order q elements in G, respectively. By Cauchy’s Theorem there is an element $g\in G$ of order p. By Lemma 2 (ii), its $n-1$ conjugates $tgt^{-1}$ ($t\in T$) are all distinct and not in T. All these conjugates have order p. So $m_{p}\ge n-1$. Similarly $m_{q}\ge n-1$.

Meanwhile, it follows from Lemma 2(iv) that

$$\begin{aligned} \left| T\cup \bigcup _{t\in T} tsTst^{-1}\right| =n(n-2)+1=n^{2}-2n+1. \end{aligned}$$

Since all the conjugates of T have order $n-1$ and $p,q\not \mid n-1$, there are no elements among the conjugates of T that have order p or q. So we have at least $(n^{2}-2n+1)+m_{p}+m_{q}$ distinct elements in G, which leads to a contradiction since

$$\begin{aligned} (n^{2}-2n+1)+m_{p}+m_{q}\ge (n^{2}-2n+1)+(n-1)+(n-1)>n(n-1)=|G|. \end{aligned}$$

$\square$

3.4 $S_{p^{m}+1,3}$ is Cayley

Lemma 3

Let p be an odd prime and $\sigma$ be a primitive root of p. We have the following group isomorphism:

$$\begin{aligned} F_{p}\rtimes F^{*}_{p}\cong \langle a,x\mid a^{p-1}=x^{p}=1,\; ax=x^{\sigma }a\rangle . \end{aligned}$$

Proof

Denote the right hand side by H. Elements in the right hand side are of the form $x^i a^j$, where $0\le i\le p-1$, $0\le j\le p-2$, so $|H|\le p(p-1)$. Consider the homomorphism

$$\begin{aligned} \psi : H\mapsto F_{p}\rtimes F^{*}_{p} \end{aligned}$$

determined by $\psi (a)=t=(0,\sigma )$, $\psi (x)=st^{\frac{p-1}{2}}=(1,1)$. It is easy to check that

$$\begin{aligned} \psi (a)^{p-1}=\psi (x)^p=(0,1)=1_{F_{p}\rtimes F^{*}_{p}},\quad \psi (a)\psi (x)=(\sigma ,\sigma )=\psi (x)^\sigma \psi (a). \end{aligned}$$

Thus $\psi$ is well-defined. Since $\psi (a)=t$, $\psi (xa^{-q})=s$, and the group $F_{p}\rtimes F^{*}_{p}$ is generated by t and s, we conclude that $\psi$ is surjective. Since $|H|\le p(p-1)={|}F_{p}\rtimes F^{*}_{p}{|}$, we conclude that $\psi$ is an isomorphism. $\square$

Lemma 4

Let $n\ge 5$, and assume that G is a group of order $n(n-1)(n-2)$ generated by a subgroup T of order $n-2$ together with two elements b and c of order 2. Let $H=\langle T,b\rangle$. Assume that $\Gamma (H, (T{\setminus }\{1\})\cup \{b\})\cong S_{n-1,2}$, $(bc)^3=1$, and

$$\begin{aligned} H\cap (bc)H(bc)^{-1}{\subseteq } T,\quad T\cap (bc)T(bc)^{-1}=\{1\}. \end{aligned}$$

Then $\Gamma (G,(T{\setminus }\{1\})\cup \{b,c\})\cong S_{n,3}$.

Proof

We shall prove that $\Gamma (G,S)\cong S_{n,3}$ for $S=(T{\setminus }\{1\})\cup \{b,c\}$ by verifying the three conditions in Lemma 2.

For (i) Let $H_1(=H),H_2,\dots ,H_n$ be the left cosets of H in G. Then by assumption, all the induced subgraphs are isomorphic to $S_{n-1,2}$.

(ii) It is easy to check that $b,bc,bcb,bcbc,bcbcb,bcbcbc(=1)$ are distinct from each other (they actually form the group $S_3$). So at every vertex v of G there is a star-like 6-cycle passing through it, namely (v, vb, vbc, vbcb, vbcbc, vbcbcb). Since each vertex of G is incident to two star-like edges, all the star-like 6-cycles are disjoint.

We claim that there is at most one star-like 6-cycle satisfying the condition in (ii). Indeed, if $(v,vb,\dots ,vbcbcb)$ and $(v',v'b,\dots ,v'bcbcb)$ are such star-like 6-cycles, then $v'\in vH$, $v'bc\in vbcH$, $v'bcbc\in vbcbcH$. Thus

$$\begin{aligned} v^{-1}v'\in H\cap (bc)H(bc)^{-1}\cap (bc)^2H(bc)^{-2}{\subseteq } T\cap (bc)T(bc)^{-1}=\{1\}, \end{aligned}$$

so $v=v'$.

The claim implies that for every unordered pair (j, k) (so that i, j, k are distinct) there is at most one star-like 6-cycle contained in $H_i\cup H_j\cup H_k$. Since there are $\left( {\begin{array}{c}n-1\\ 2\end{array}}\right)$ such unordered pairs, there are at most $\left( {\begin{array}{c}n-1\\ 2\end{array}}\right)$ star-like 6-cycles intersecting with $H_i$. On the other hand, there are $\frac{|H_i|}{2}=\left( {\begin{array}{c}n-1\\ 2\end{array}}\right)$ star-like edges in $H_i$, and each vertex in $H_i$ is incident to exactly one such edge, so there should be exactly $\left( {\begin{array}{c}n-1\\ 2\end{array}}\right)$ star-like 6-cycles intersecting with $H_i$. Therefore for every unordered pair (j, k) (so that i, j, k are distinct) there is exactly one star-like 6-cycle contained in $H_i\cup H_j\cup H_k$. This implies (ii).

(iii) Since $v_{kji},v_{\ell ji}\in H_i$, and $v_{kji}bc,v_{\ell ji}bc\in H_j$, we get

$$\begin{aligned} v_{kji}^{-1}v_{\ell ji}\in H\cap (bc)H(bc)^{-1}{\subseteq } T. \end{aligned}$$

So $v_{kji}$ and $v_{\ell ji}$ are joined by a residual-like edge. $\square$

Proposition 6

If p is a prime number and m is a positive integer, then $S_{p^{m}+1,3}$ is a Cayley graph.

Proof

We prove the statement by verifying the conditions in Lemma 4.

Let $n=p^{m}+1$, $q=p^{m}$, $G=\mathrm{PGL}(2,q)$, $S=\{A^{i}\mid i=1,\dots ,q-1\}\cup \{B,C\}$ where

$$\begin{aligned} A=\begin{bmatrix} \sigma&\quad 0\\ 0&\quad 1 \end{bmatrix}, \quad B=\begin{bmatrix} -1&\quad 1\\ 0&\quad 1 \end{bmatrix}, \quad C=\begin{bmatrix} -1&\quad 0\\ -1&\quad 1 \end{bmatrix}. \end{aligned}$$

First, $|G|=n(n-1)(n-2)$. Indeed, it is well known that $|\mathrm{GL}(2,q)|=(q^{2}-1)(q^{2}-q)$, so $|G|=(q^{2}-1)(q^{2}-q)/(q-1)=(q+1)q(q-1)=n(n-1)(n-2)$.

Then we show that A, B, C generate G. Indeed, the cyclic group

$$\begin{aligned} T=\langle A\rangle =\bigg \{\begin{bmatrix} a&\quad 0\\ 0&\quad 1 \end{bmatrix}\bigg | \;a\ne 0\bigg \}=\bigg \{\begin{bmatrix} a&\quad 0\\ 0&\quad b \end{bmatrix}\in \mathrm{PGL}(2,q)\bigg \} \end{aligned}$$

has order $(n-2)$ and contains all diagonal matrices in G. Then A and B generate $B\begin{bmatrix} -1&\quad 0\\ 0&\quad 1 \end{bmatrix} =\begin{bmatrix} 1&\quad 1\\ 0&\quad 1 \end{bmatrix}$, which generates all matrices $\begin{bmatrix} 1&\quad a\\ 0&\quad 1 \end{bmatrix}$ for $a\in F_{q}$. So A and B generate all the upper triangular matrices. Then note that $BCB=\begin{bmatrix} 0&\quad 1\\ 1&\quad 0 \end{bmatrix}$, so all the elementary matrices can be generated by A, B, C. Using elementary matrices and upper triangular matrices we can generate G.

It is straightforward to check that B and C have order 2, and $(BC)^{3}=\begin{bmatrix} 1&\quad 0\\ 0&\quad 1 \end{bmatrix}$.

It follows from (2) and Proposition 5 that

$$\begin{aligned} H=\langle T,B\rangle =\langle A,B\rangle =\bigg \{\begin{bmatrix} b&\quad a\\ 0&\quad 1 \end{bmatrix}\in \mathrm{PGL}(2,q)\bigg \}\cong F_q\rtimes F^{*}_q \end{aligned}$$

and $\Gamma (H, S{\setminus }\{C\})\cong S_{q,2}$.

Next we verify $H\cap (BC)H(BC)^{-1}{\subseteq } T$. For any

$$\begin{aligned} D=\begin{bmatrix} b&\quad a\\ 0&\quad 1 \end{bmatrix}\in H\cap (BC)H(BC)^{-1}, \end{aligned}$$

we have

$$\begin{aligned} (BC)^{-1}D(BC)= \begin{bmatrix}-a+1&\quad a+b-1\\ -a&\quad a+b \end{bmatrix}\in H, \end{aligned}$$

implying that $a=0$. Thus $D\in T$.

Finally we check $T\cap (BC)T(BC)^{-1}=\{1\}$. In the above assume further that $D\in T\cap (BC)T(BC)^{-1}$. Then $a=0$ and $b=1$. So $D=\begin{bmatrix} 1&\quad 0\\ 0&\quad 1 \end{bmatrix}$. $\square$

4 Conclusions

We have studied the question of which (n, k)-star graphs are Cayley. The conclusion that they are sometimes but not always Cayley could be seen as surprising since most of the other widely studied interconnection networks are Cayley graphs. The results in this paper also provide new insight into the structure of (n, k)-star graphs.

It would be desirable to ultimately find a complete classification. Although this may prove to be a very difficult problem, there are some next steps that might be tractable. First, we conjecture that the condition given in Proposition 6 is both necessary and sufficient, giving the following.

Conjecture 1

$S_{n,3}$ is Cayley if and only if $n-1$ is a prime power.

Additionally, we believe that the methods applied in this paper may lead to insight into the structure of $S_{n,k}$ for other small values of k.

Our results also lead us to make another conjecture.

Conjecture 2

If $S_{n,k}$ is Cayley and $k\ge 2$, then $S_{n-1,k-1}$ is Cayley.

There are two reasons why we believe this might be the case. First, our results in Proposition 6 and Theorem 3, and all other results in the paper match up in a way consistent with this conjecture. Second, as $S_{n,k}$ contains many subgraphs of $S_{n-1,k-1}$, we think it is possible that non-Cayley subgraphs of $S_{n-1,k-1}$ may indicate structural properties that could also prevent $S_{n,k}$ from being Cayley. We remark that the converse of Conjecture 2 is not true as $S_{5,1}$ is Cayley but $S_{6,2}$ is not Cayley. Nevertheless it may still be true for certain values of k.

As a final note, we observe that since the (n, k)-star graphs are well studied and have been shown to have a wide variety of nice structural properties, they could be used as counterexamples to conjectures about sufficient conditions for graphs being Cayley.