A133181 Number of distinct connected simple symmetric (edge- and vertex-transitive) graphs with n nodes.

1, 1, 1, 2, 2, 4, 2, 5, 4, 8, 2, 11, 4, 8, 10

Offset

1,4

Comments

Care is needed with "symmetric" terminology, which is variously used to mean both arc-transitive and both vertex- and edge-transitive.

The symmetry means that any two vertices and any two edges are equivalent. In other words, if we have an initial labeling of the graph with vertices A and B adjacent (directly connected by an edge), we can relabel any two adjacent vertices as A and B and then relabel the remaining vertices so that new graph will be equal to the initial.

The first known difference from A286280 (connected arc-transitive graphs on n vertices) occurs at a(27), corresponding to the Doyle graph (which is both edge- and vertex-transitive but not arc-transitive). - Eric W. Weisstein, May 13 2017

By convention, empty graphs are considered edge-transitive (and hence symmetric).

Links

Table of n, a(n) for n=1..15.

Eric Weisstein's World of Mathematics, Arc-Transitive Graph

Eric Weisstein's World of Mathematics, Doyle Graph

Eric Weisstein's World of Mathematics, Edge-Transitive Graph

Eric Weisstein's World of Mathematics, Symmetric Graph

Eric Weisstein's World of Mathematics, Vertex-Transitive Graph

Example

The complete graph is symmetrical.
In addition, if the number of vertices is > 3, the simple cycle through all vertices is symmetrical.
Graphs determined by vertices and edges of Platonic solids are symmetrical.
The square K X K grid with right vertices connected to corresponding left vertices and bottom vertices connected to corresponding top vertices is symmetrical.
The smallest nontrivial and non-Platonic symmetric graph is the hexagon with connected opposite vertices.
An example of a symmetrical graph with 13 vertices:
   0 connected to 1, 2,  3,  4
   1 connected to 0, 5,  6,  7
   2 connected to 0, 5,  8,  9
   3 connected to 0, 6, 10, 11
   4 connected to 0, 8, 10, 12
   5 connected to 1, 2, 10, 11
   6 connected to 1, 3,  8, 12
   7 connected to 1, 8,  9, 11
   8 connected to 2, 4,  6,  7
   9 connected to 2, 7, 10, 12
  10 connected to 3, 4,  5,  9
  11 connected to 3, 5,  7, 12
  12 connected to 4, 6,  9, 11

Crossrefs

Cf. A087145 (number of disconnected simple symmetric graphs on n nodes).

Cf. A286931 (number of not necessarily connected simple symmetrical graphs with n nodes).

Cf. A286280 (number of connected arc-transitive graphs of order n).

Sequence in context: A139555 A241814 A088371 * A286280 A290088 A179013

Adjacent sequences: A133178 A133179 A133180 * A133182 A133183 A133184

Keyword

hard,more,nice,nonn

Author

Eugene Vasilchenko (eugene(AT)vasilchenko.net), Oct 10 2007, Oct 14 2007

Extensions

a(1) and a(2) changed from 0 to 1 (since K_1 and K_2 are connected, vertex-transitive, and edge-transitive) by Eric W. Weisstein, May 16 2017

Status

approved