Generalized Earl of Petersen

In the Watkins notation, G ( n , k ) is a graph with many vertices

{ u ₀ , u ₁ , ..., u _{n −1} , v ₀ , v ₁ , ..., v _{n −1} }

and many ribs

{ u _i u _{i +1} , u _i v _i , v _i v _{i + k} : i = 0, ..., n - 1}

where the indices are taken modulo n and k < n / 2. Coxeter’s designation for the same graph is { n } + { n / k }, a combination of the Schlefli symbol for the regular n- gon and the star from which the graph is formed. Any generalized Petersen graph can be constructed as a from a graph with two vertices, two loops and another edge ^[3] .

The Petersen graph itself is G (5.2) or {5} + {5/2}.

Among the generalized Petersen graphs are the n- prism G ( n , 1), the Dürer graph G (6,2), the Mobius – Cantor graph G (8,3), the dodecahedron G (10,2), the Desargues graph G (10,3 ) and the graph of Nauru G (12.5).

Four generalized Petersen graphs - a triangular prism, a 5-angle prism, a Dürer graph, and G (7,2) are included in seven graphs that are cubic , vertex 3-connected, and well-covered (which means that all its largest independent sets have one and the same size) ^[4] .

This family of graphs has a number of interesting properties. For example:

1. G ( n , k ) is vertex-transitive (means that there are symmetries that translate any vertex to any other) if and only if n = 10 and k = 2 or if k ² ≡ ± 1 (mod n ).
2. It is edge-transitive (having symmetries that take any edge to any other) only in the following seven cases: ( n , k ) = (4,1), (5,2), (8,3), (10,2 ), (10.3), (12.5), (24.5) ^[5] . Only these seven graphs are symmetric generalized Petersen graphs.
3. It is bipartite if and only if n is even and k is odd.
4. He is a Cayley graph if and only if k ² ≡ 1 (mod n ).
5. It is if n is comparable to 5 modulo 6 and k is 2, n −2, ( n +1) / 2, or ( n −1) / 2 (all four of these values ​​of k lead to isomorphic graphs). It is not Hamiltonian if n is divisible by four, at least at a value of 8, and k is equal to n / 2. In all other cases, it has a Hamiltonian cycle ^[6] . If n is comparable to 3 modulo 6 and k is 2, G ( n , k ) has exactly three Hamiltonian cycles ^[7] , for G ( n , 2) the number of Hamiltonian cycles can be calculated by a formula depending on classes of n modulo six , and involves Fibonacci numbers ^[8] .

The Petersen graph is the only generalized Petersen graph that cannot be colored in edges in 3 colors ^[9] . The generalized Petersen graph G (9.2) is one of the few well-known graphs that cannot be ^[10] .

Any generalized Petersen graph is a unit distance graph ^[11] .