generalizedPetersen Class Reference
[Graph series]

A family 3-node regular, usually non-planar graphs with high girth. More...

#include <sparseGraph.h>

Inheritance diagram for generalizedPetersen:

sparseGraph abstractGraph abstractMixedGraph managedObject goblinRootObject

Public Member Functions

 generalizedPetersen (TNode perimeter, TNode skew, goblinController &_CT=goblinDefaultContext) throw (ERRejected)

Detailed Description

A family 3-node regular, usually non-planar graphs with high girth.

Constructor & Destructor Documentation

generalizedPetersen TNode  perimeter,
TNode  skew,
goblinController _CT = goblinDefaultContext
throw (ERRejected)

Generate a Petersen like graph.

perimeter The length of the exterior cycle
skew Some value in the interval (0, .., perimeter)
_CT The controller object to manage the created graph
This generates a graph which consists of two equal cardinality node sets. The subgraph induced by the set 0, 1, .., perimeter-1 of exterior nodes forms a cycle. Exterior and interior nodes are joined by the edges (i, perimeter+i) with i in the interval [0, .., perimeter). Interior nodes are joined by the edges (perimeter+i, perimeter+(i+skew)perimeter).

In the regular setting, perimeter and skew are relatively prime, and the subgraph induced by the second node set perimeter, perimeter+1, .., 2*perimeter-1 also forms a cycle, but the node order is determined by the skew parameter. In any case, the generated graph is 3-node regular.

Up to the implicit arc orientations of the interior cycle, skew = k and skew = perimeter-k give the same graph. For skew == 1, the result is a prism. For skew == 2 and even perimeter, the result is planar.

The original Petersen graph is given by generalizedPetersen(5,2). Some other graphs in this family have received special attention:

  • generalizedPetersen(6,2) is known as the Duerer graph,
  • generalizedPetersen(8,3) is known as the Moebius-Cantor graph,
  • generalizedPetersen(10,2) is the dodecahedron,
  • generalizedPetersen(10,3) is known as the Desargues graph.