On 3-regular 4-ordered graphs (Q2483395)

A characterization of smallest 3-regular 4-ordered (hamiltonian) graphs with girth at least 5 is given. A simple graph G is 4-ordered (hamiltonian), when for any 4-permutation of its vertices exists a (hamiltonian) cycle passing through these vertices in given order. In the paper, it is proved that the smallest 3-regular 4-ordered graph with the girth at least 5 is the Petersen graph, and the smallest 3-regular 4-ordered hamiltonian graph with the girth at least 6 is the Heawood graph. Also an infinite family of 3-regular 4-ordered graphs of a graph is introduced.