Seminar on Combinatorics

主講者: | 徐力行教授 (靜宜大學資工系) |

講題: | Solution to an open problem on 4-ordered Hamiltonian graphs |

時間: | 2012-01-13 (Fri.) 10:30 - 11:30 |

地點: | 數學所 617 研討室 (台大院區) |

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 specied order. It is k-ordered Hamiltonian if, in addition, the required cycle is Hamiltonian. The question of the existence of an innite class of 3-regular 4-ordered Hamiltonian graphs was posed in 1997. At the time, the only known examples were K4 and K3;3. Some progress was made in 2008 when the Peterson graph was found to be 4-ordered and the Heawood graph was proved to be 4-ordered Hamiltonian; moreover an innite class of 3-regular 4-ordered graphs was found. In this paper we show that a subclass of generalized Petersen graphs are 4-ordered and give a complete classication for which of these graphs are 4-ordered Hamiltonian. In particular, this answers the open question regarding the existence of an innite class of 3-regular 4-ordered Hamiltonian graphs. Moreover, a number of results related to other open problems are presented. |

|| Close window || |