Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

Journal of Inforamtion Science and Engineering, Vol.17 No.4, pp.535-548 (July 2001)

A Family of Trivalent 1-Hamiltonian Graphs
With diameter O(log n)

Jeng-Jung Wang, Ting-Yi Sung* and Lih-Hsing Hsu
 Department of Computer and Information Science
National Chiao Tung University
Hsinchu, Taiwan 300, R.O.C.
E-mail: lhhsu@cc.nctu.edu.tw
*Institute of Information Science
Academia Sinica
Taipei, Taiwan 115, R.O.C.

In this paper, we construct a family of graphs denoted by Eye(s) that are 3-regular, 3-connected, planar, hamiltonian, edge hamiltonian, and also minimal 1-hamiltonian. Furthermore, the diameter of Eye(s) is O(log n), where n is the number of vertices in the graph and to be precise, n = 6(2s - 1) vertices.

Keywords: hamiltonian, edge hamiltonian, 1-vertex hamiltonian, 1-edge hamiltonian, 1-hamiltonian, diameter, Moore bound

Full Text (¥þ¤åÀÉ) Retrieve PDF document (200107_01.pdf)

Received April 30, 1999; revised December 17, 1999; accepted February 24, 2000.
Communicated by Jang-Ping Sheu.