Abstract
In this paper, we construct a family of graphs denoted by Eye(s) that are 3-regualr, 3-connected, planar, hamiltonian, edge hamiltonian, and also optimal 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.
This work was supported in part by the National Science Council of the Republic of China under contract NSC86-2213-E009-020.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, North-Holland, New York, (1980).
F.R.K. Chung, Diameters of graphs: Old problems and new results, Proc. 18th South-Eastern Conf. Combinatorics, Graph Theory, and Computing, Congressus Numerantium, 60(1987), 298–319.
F. Harary and J.P. Hayes, Edge fault tolerance in graphs, Networks, 23(1993), 135–142.
F. Harary and J.P. Hayes, Node fault tolerance in graphs, Networks, 27(1996), 19–23.
P. Horák and J. Širáň, On a construction of Thomassen, Graphs and Combinatorics, 2(1986), 347–350.
K. Mukhopadhyaya and B.P. Sinha, Hamiltonian graphs with minimum number of edges for fault-tolerant topologies, Information Processing Letters, 44(1992), 95–99.
L. Stacho, Maximally non-hamiltonian graphs of girth 7, Graphs and Combinatorics, 12(1996), 361–371.
C. Thomassen, Hypohamiltonian and hypotraceable graphs, Discrete Math., 9(1974), 91–96.
J.J. Wang, C.N. Hung, and L.H. Hsu, Optimal 1-hamiltonian graphs, accepted by Information Processing Letters.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wang, JJ., Sung, TY., Hsu, LH., Lin, MY. (1998). A New Family of Optimal 1-Hamiltonian Graphs with Small Diameter. In: Hsu, WL., Kao, MY. (eds) Computing and Combinatorics. COCOON 1998. Lecture Notes in Computer Science, vol 1449. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-68535-9_31
Download citation
DOI: https://doi.org/10.1007/3-540-68535-9_31
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64824-6
Online ISBN: 978-3-540-68535-7
eBook Packages: Springer Book Archive