JISE

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

Journal of Information Science and Engineering, Vol. 17 No. 4, pp. 535-548

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

Retrieve PDF document (JISE_200104_01.pdf)