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

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.