On k-step Hamiltonian bipartite and tripartite graphs

Gee-Choon Laua,*, Sin-Min Leeb, Karl Schafferc and Siu-Ming Tongd

On k-step Hamiltonian bipartite and tripartite graphs

Authors :

Gee-Choon Lau^a^,*, Sin-Min Lee^b, Karl Schaffer^c and Siu-Ming Tong^d

Author Address :

^aFaculty of Comp. & Mathematical Sciences, Universiti Teknologi MARA, 40450 Shah Alam,Malaysia .
^b34803,Hollyhock St., Union City, CA 94587, USA.
^cDept. of Mathematics, De Anza College, Cupertino, CA 95014,USA.
^dDept. of Computer Science, Northwestern Polytechnic University, Fremont, CA 94539,USA.

* Corresponding author.

Abstract :

For integer $kge 1$, a $(p,q)$-graph $G = (V,E)$ is said to admit an $AL(k)$-traversal if there exist a sequence of vertices $(v_1,v_2,ldots,v_p)$ such that for each $i =1,2,ldots,p-1$, the distance for $v_i$ and $v_{i+1}$ is $k$. We call a graph $k$-step Hamiltonian (or admits a $k$-step Hamiltonian tour) if it has an $AL(k)$-traversal and $d(v_1,v_p)=k$. In this paper we consider $k$-step Hamiltonicity of bipartite and tripartite graphs. As an application, we found that a 2-step Hamiltonian tour of a graph could sometimes induce a super-edge-magic labeling of the graph.

Keywords :

Hamiltonian tour, 2-step Hamiltonian tour, bipartite $&$ tripartite graphs, NP-complete problem, super-edge-magic labeling.

DOI :

Article Info :

Received : October 29, 2013; Accepted : February 26, 2014.