Abstract

A simple undirected graph is said to be semisymmetric if it is regular and edge-transitive but not vertex-transitive. This paper uses finite groups to construct many infinite families of such graphs.

Introduction

There is an intimate relationship between groups and graphs. For example, any graph X gives rise to its automorphism group A := Aut(X). On the other hand, any group G with generating set S gives rise to its Cayley graph Cay(G, S). The main purpose of this paper is to show how groups can be used to construct examples of semisymmetric graphs, graphs which are regular and edge-transitive but not vertex-transitive. [Relevent definitions are given in Section 2.]

These semisymmetric graphs were first systematically studied in 1967 by J. Folkman [6]. For later works on semisymmetric graphs, the reader is referred to [1, 2, 3, 4, 5, 7, 8, 9].

Since the known semisymmetric graphs are not many and since they have very special symmetry properties, there is a common belief that semisymmetric graphs are rare in number. We do not share this belief since our contruction leads to infinite classes of such graphs.

This paper is organized as follows. First we give the necessary notation, definitions, and concepts needed for this paper, including that of semisymmetric graphs. In particular, we introduce the notion of co-neighbor blocks and noncontractable graphs, and we also give the definition of a bi-lexicographic product of a graph.