On Hamiltonian-Connected Graphs

Abstract

INTRODUCTION

Graphs are present in almost all sciences, mathematics, and engineering. From the ground, as to how geologists map the world and dig the minerals beneath the grounds, to how biologists and chemists answer how life exists and works, and to how astronomers discover and uncover the mystery of the universe. Indeed, graph theory has one of the broadest and widest applications. Thus, studies of graphs will not only contribute to the existing theories of scientific knowledge but as well as to industries and society.

METHODS

This study is an investigation of the properties and conditions for Hamiltonian connected graphs to be Hamiltonian connected bipartite graphs. Novel results on these graphs were presented and proved.

RESULTS

Theorem 3.2: Let G be a complete bipartite graph, G is Hamiltonian-connected if and only if G has a bipartition. Proof:

To show that complete bipartite graph with bipartition is Hamiltonian-connected, let G be a complete bipartite graph with and.

Since each vertex in V1 is connected to V2 (See Figure 1), then we can construct a Hamiltonian-connected graph with.

We now show that a complete bipartite Hamiltonian-connected graph has bipartition. By contradiction let G be a Hamiltonian-connected complete bipartite graph with bipartition. Suppose and, then. If and, let and, since it is a complete bipartite graph, every element in V1 is connected to each element in V2, that is, we cannot see any cycle in the resulting graph, so, therefore, it is not a Hamiltonian graph; hence, not a Hamiltonian connected graph. Similar results follow for any. Therefore, by contradiction a Hamiltonian-connected complete bipartite graph G has bipartition.

DISCUSSIONS

A graph, as defined in graph theory, consists of a pair (V, E) where V is a nonempty finite set whose elements are called vertices and E is a set of unordered pairs of distinct elements of V. One interesting kind of graph is the Hamiltonian graph, named after William Rowan Hamilton, who invented the famous icosian game, which is the game of finding a Hamiltonian cycle. A graph G is said to be Hamiltonian if it has a Hamiltonian cycle, and for a Hamiltonian graph G to be Hamiltonian-Connected, there must be a Hamiltonian path between every pair of vertices in it. The result gives us sufficient condition for a Hamiltonian-connected graph to be a complete bipartite graph.