Symmetric Graph

A symmetric graph is defined in two different ways in the literature. Following Harary and Palmer (1973, p. 263), Leighton (1983), and Holton and Sheehan (1993, p. 209), this work calls a graph symmetric if it is both edge-transitive and vertex-transitive.

Under another common convention, especially in algebraic graph theory, "symmetric graph" is a synonym for arc-transitive graph (Godsil and Royle 2001, p. 59; Conder et al. 2015). Every symmetric graph in this second sense is symmetric in the first sense, but the converse is false. A graph that is vertex-transitive and edge-transitive but not arc-transitive is called a half-arc-transitive graph (Conder and Žitnik 2016). It is symmetric under the convention used in this work, but not under the arc-transitive convention.

A regular graph that is edge-transitive but not vertex-transitive is called a semisymmetric graph.

Neither the graph complement nor the line graph of a symmetric graph is necessarily symmetric.

Symmetric graphs are always regular graphs. The number of symmetric graphs on , 2, ... nodes are 1, 2, 2, 4, 3, 7, 3, 9, ..., a few of which are illustrated above. These are the complete graph ; cycle graph , ; , ; , circulant graph , , octahedral graph, and .

A list of other named symmetric graphs is given in the table below.

graph	vertices
tetrahedral graph	4
complete graph	5
octahedral graph (circulant graph )	6
(utility graph)	6
complete graph	6
16-cell	8
cubical graph	8
Petersen graph	10
cuboctahedral graph	12
icosahedral graph	12
Heawood graph	14
Clebsch graph	16
Moebius-Kantor graph	16
tesseract	16
Pappus graph	18
dodecahedral graph	20
Desargues graph	20
Doyle graph	27
Coxeter graph	28
Tutte 8-cage	30
icosidodecahedral graph	30
Dyck graph	32
Foster graph	90
Biggs-Smith graph	102