$GI$-graphs: a new class of graphs with many symmetries

Conder, Marston D.E. ; Pisanski, Tomaž ; Žitnik, Arjana

Journal of Algebraic Combinatorics, Tome 40 (2014) no. 1, pp. 209-231.

Résumé

The class of generalized Petersen graphs was introduced by Coxeter in the 1950s. R. Frucht et al. [Proc. Camb. Philos. Soc. 70, 211--218 (1971; Zbl 0221.05069)] determined the automorphism groups of generalized Petersen graphs, and much later, R. Nedela and M. Škoviera [J. Graph Theory 19, No. 1, 1--11 (1995; Zbl 0812.05026)] and (independently) M. Lovrečič-Saražin [J. Comb. Theory, Ser. B 69, No. 2, 226--229 (1997; Zbl 0867.05027)] characterised those which are Cayley graphs. In this paper we extend the class of generalized Petersen graphs to a class of $GI$-graphs. For any positive integer $n$ and any sequence $j_{0},j_{1},\dots,j_{t-1}$ of integers mod $n$, the $GI$-graph $GI(n;j_{0},j_{1},\dots,j_{t-1})$ is a $(t+1)$-valent graph on the vertex set $\mathbb{Z}_{t} \times\mathbb{Z}_{n}$, with edges of two kinds: (i) an edge from $(s,v)$ to $(s^\prime,v)$, for all distinct $s,s^\prime \in \mathbb{Z}_{t}$ and all $v \in\mathbb{Z}_{n}$, (ii) edges from $(s,v)$ to $(s,v+j_{s})$ and $(s,v-j_{s})$, for all $s \in \mathbb{Z}_{t}$ and $v \in \mathbb{Z}_{n}$. By classifying different kinds of automorphisms, we describe the automorphism group of each $GI$-graph, and determine which $GI$-graphs are vertex-transitive and which are Cayley graphs. A $GI$-graph can be edge-transitive only when $t\leq 3$, or equivalently, for valence at most 4. We present a unit-distance drawing of a remarkable $GI(7;1,2,3)$.

Détail

Classification : 05C25
Keywords: $GI$-graph, generalized Petersen graph, vertex-transitive graph, edge-transitive graph, circulant graph, automorphism group, wreath product, unit-distance graph