Classification of Symmetric Tabajn Graphs

A bicirculant is a graph admitting an automorphism whose cyclic decomposition consists of two cycles of equal length. In this paper we introduce the Tabajn graphs, a family of pentavalent bicirculants which are a natural generalization of generalized Petersen graphs obtained from them by adding two additional perfect matchings between the two orbits of a semiregular automorphism. The main result is the classification of symmetric Tabajn graphs. In particular, it is shown that the only such graphs are the complete graph , the complete bipartite graph minus a perfect matching and the icosahedron graph.