Brother trees: A family of optimal 1(p)-hamiltonian and 1-edge hamiltonian graphs

Title:	Brother trees: A family of optimal 1(p)-hamiltonian and 1-edge hamiltonian graphs
Authors:	Kao, SS Hsu, LH 資訊工程學系 Department of Computer Science
Keywords:	hamiltonian;diameter;complete binary tree;interconnection networks
Issue Date:	15-Jun-2003
Abstract:	In this paper we propose a family of cubic bipartite planar graphs, brother trees, denoted by BT(n) with n greater than or equal to 2. Any BT(n) is hamiltonian. It remains hamiltonian if any edge is deleted. Moreover, it remains hamiltonian when a pair of nodes (one from each partite set) is deleted. These properties are optimal. Furthermore, the number of nodes in BT(n) is 6. 2(n) - 4 and the diameter is 2n + 1. (C) 2003 Elsevier Science B.V. All rights reserved.
URI:	http://dx.doi.org/10.1016/S0020-0190(02)00509-4 http://hdl.handle.net/11536/27790
ISSN:	0020-0190
DOI:	10.1016/S0020-0190(02)00509-4
Journal:	INFORMATION PROCESSING LETTERS
Volume:	86
Issue:	5
Begin Page:	263
End Page:	269
Appears in Collections:	Articles

Files in This Item:

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.