## Abstract

A graph G is k-ordered if for any sequence of k distinct vertices of G, there exists a cycle in G containing these k vertices in the specified order. It is k-ordered Hamiltonian if, in addition, the required cycle is Hamiltonian. The question of the existence of an infinite class of 3-regular 4-ordered Hamiltonian graphs was posed in 1997 by Ng and Schultz. At the time, the only known examples were K_{4} and K_{3,3}. Some progress was made in 2008 by Mészáros, when the Peterson graph was found to be 4-ordered and the Heawood graph was proved to be 4-ordered Hamiltonian; moreover, an infinite class of 3-regular 4-ordered graphs was found. In 2010 a subclass of generalized Petersen graphs was shown to be 4-ordered by Hsu et al., with an infinite subset of this subclass being 4-ordered Hamiltonian, thus answering the open question. In this paper we find another infinite class of 3-regular 4-ordered Hamiltonian graphs, part of a subclass of the chordal ring graphs. In addition, we classify precisely which of these graphs are 4-ordered Hamiltonian.

Original language | English (US) |
---|---|

Pages (from-to) | 157-174 |

Number of pages | 18 |

Journal | Journal of Interconnection Networks |

Volume | 11 |

Issue number | 3-4 |

DOIs | |

State | Published - 2010 |

### Bibliographical note

Funding Information:∗Research partially supported by the NSF-REU Grant DMS 0649099. †Research partially supported by the NSF-REU Grant DMS 0649099. ‡Corresponding author. Research partially supported by the NSF-REU Grant DMS 0649099.

## Keywords

- 4-ordered
- Chordal ring graphs
- Hamiltonian