The Petersen Graph in Diversity

03 Oct 2014

In (Wester, 1994) an influential list of 123 problems that a reasonable computer algebra system (CAS) should be able to solve is presented. In this post we begin creating a similar list of problems in graph theory that a reasonable graph analysis system (GAS) ought to be able to solve.

The inspiration for this list comes from Chapter 9 of (Holton & Sheehan, 1993 ) from where the title of this post is borrowed. That chapter presents many different definitions of the Petersen graph. The aim of this post is to implement as many of them as possible. The post will be updated as more implementations are discovered.

The Petersen Graph

The Petersen graph gets its name from its appearance in the paper (Petersen, 1898) of J. Petersen as a counterexample to Tait’s claim that ‘every bridgeless cubic graph is 1-factorable’. This was not the first time the Petersen graph appeared in the literature of graph theory and far from the last. Since then it has appeared in a great many publications, often as a counterexample to a new conjecture.

Definitions of the Petersen graph arise in different ways. As direct constructions (for example by identifying antipodal points in the graph of the dodecahedron) or indirectly as one of a class of graphs satisfying certain properties (one of the bridgeless cubic graphs which are not 1-factorable).

In this post we being to collect as many different definitions as possible and give implementations of constructions or filters based on list of properties. The purpose of this is several-fold

to initiate an effort to formulate a list of problems that a reasonable GAS ought to be able to solve,
to motivate the development of tools for graph analysis on the command-line,
to create test cases for a collection of graph data.

The third of these motivations is something that we will return to in future posts.

Below are two lists. The latter is a collection of properties of the Petersen graph. The first is a list of definitions. To avoid repetition, if a single property defines the Petersen graph uniquely then it appears in the first list only.

In both lists $C (n)$ denotes the set of connected cubic graphs of order $n$ .

The canonical graph6 encoding of the Petersen graph is IsP@OkWHG.

The Definition List

The complement of the line graph of $K_{5}$ .

       $ geng -q -d4D4 5 | linegraphg -q | complg -q | labelg -q
       IsP@OkWHG

The unique Moore graph of order 10.

       $ geng -qc 10 | moore.py | labelg -q
       IsP@OkWHG

The only graph in $C (10)$ with 120 automorphisms.

       $ geng -qc 10 -d3D3 | pickg -q -a120 | labelg -q
       IsP@OkWHG

The only graph in $C (10)$ with girth 5.

       $ paste <(geng -qc 10 -d3D3) <(geng -qc 10 -d3D3 | girth.py)\
        | awk '{ if ($2==5) print $1 }'\
        | labelg -q
       IsP@OkWHG

The only graph in $C (10)$ with diameter 2.

       $ paste <(geng -qc 10 -d3D3) <(geng -qc 10 -d3D3 | diameter.py)\
        | awk '{ if ($2==2) print $1 }'\
        | labelg -q
       IsP@OkWHG

The Kneser graph $K_{5, 2}$ .

       $ maxima --very-quiet --batch-string="\
          load(graphs)$
          s : powerset({`seq 1 5 | paste -s -d,`}, 2)$
          g : make_graph(s, disjointp)$
          graph6_encode(g);
         "\
         | tail -n 1\
         | tr -d ' \t\r\f'\
         | labelg -q
         IsP@OkWHG

The Odd graph $O (3)$ .
The Moore graph with degree 3 and girth 5.
The graph in $C (10)$ with the most spanning trees (2000).
The smallest bridgeless cubic graph with no 3-edge-colouring.
The only bridgeless graph in $C (10)$ with chromatic number 4.
The only non-hamiltonian graph in $C (10)$ .
The graph obtained from the dodecahedron graph by identifying antipodal vertices.
The subgraph of $G_{1} = \bar{T (7)}$ induced by $N (12)$ .
The graph whose vertices are the 21 transpositions in $S_{7}$ whose edges join vertices that represent commuting transpositions.
One of only twelve connected cubic graphs with integral spectra.
Every orientation has diameter at least 6.
Every strongly connected orientation has a directed cycle of length 5.
Is 2-connected and all dominating cycles have length $< n$ .
Is 1-tough $α \leq k + 1$ , $k \geq 3$ and non-hamiltonian.
Pancyclic and has no cycle of length 4, 5, 6 or 7 or one of two other graphs.
The complement of the Johnson graph $J (5, 2)$ .
As a uniform subset graph with parameters $(5, 2, 0)$ or $(5, 3, 1)$ .
As the projective planar dual of $K_{6}$ .
The unique generalised Petersen graph with $χ = 4$ .

The Properties List

name – Petersen Graph

order – 10

size – 15

chromatic-number – 3

chromatic-index – 4

diameter – 2

edge-connectivity – 4

girth – 5

independence-number – 4

maximum-degree – 3

radius – 2

spectrum – ${3, 1^{5}, - 2^{4}}$

vertex-connectivity – 3

Future Directions

As of 3/10/14 there 5 of 25 definitions with full implementation. The property list contains 8 items.

Plans for the immediate future are to complete the property list and to incorporate the property list data into the testing system of the graphs-collection project.

Beyond this, the medium-term goal is to extend the list of definitions and provide implementations where possible.

In the long-term we hope to extend and generalise the list to devise a list of problems that a GAS ought to be able to solve in analogy with Wester’s list of computer algebra problems.

References

Wester, M. (1994). A Review of CAS Mathematical Capabilities. Computer Algebra Nederland Nieuwsbrief, 13, 41–48.
Holton, D. A. (D. A., & Sheehan, J. ( 1993 ). The Petersen graph . Book; Book/Illustrated , Cambridge [England] : Cambridge University Press .
Petersen, J. (1898). Sur le théorème de Tait. L’Intermédiaire Des Mathématiciens, 5, 225–227.

Coding with Graphs graph theory in code

The Petersen Graph in Diversity