On k-step Hamiltonian Bipartite and Tripartite Graphs

Gee-Choon Lau; Sin-Min Lee; Karl Schaffer; Siu-Ming Tong

doi:10.26637/mjm203/001

Abstract

For integer $k \geq 1$ , a $(p, q)$ -graph $G=(V, E)$ is said to admit an $A L(k)$ -traversal if there exist a sequence of vertices $\left(v_1, v_2, \ldots, v_p\right)$ such that for each $i=1,2, \ldots, p-1$ , the distance between $v_i$ and $v_{i+1}$ is $k$ . We call a graph $k$ -step Hamiltonian (or admits a $k$ -step Hamiltonian tour) if it admits an $A L(k)$ -traversal and $d\left(v_1, v_p\right)=$ $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

Mathematics Subject Classification:

05C78, 05C25

Authors Imprint References Funding Related Articles Downloads

Gee-Choon Lau Faculty of Comp. & Mathematical Sciences, Universiti Teknologi MARA, 40450Shah Alam, Malaysia. https://orcid.org/0000-0002-9777-6571
Sin-Min Lee 4803,Hollyhock St., Union City, CA 94587,USA.
Karl Schaffer Dept. of Mathematics, De Anza College, Cupertino, CA 95014,USA.
Siu-Ming Tong Dept. of Computer Science, Northwestern Polytechnic University, Fremont, CA 94539,USA.

Pages: 180-187
Date Published: 01-07-2014
Vol. 2 No. 03 (2014): Malaya Journal of Matematik (MJM)

T.S.N. Akiyama, T. Nishizeki, NP-completeness of the HamiltonianCycle Problem for Bipartite Graphs, Journal of Information Processing, 3(1980), 73–76.

J.-C. Bermond, Hamiltonian Graphs. In Selected Topics in Graph Theory. Edited by L. W. Beineke and R. J. Wilson. Academic, London(1978), 127–167.

G. Chartrand and P. Zhang, Introduction to Graph Theory, Walter Rudin Student Series in Advanced Mathematics, McGraw-Hill, 2004.

Z. Chen, On super edge-magic graphs, J. of Comb. Math. Comb. Comput., 38 (2001), 53–64.

V.V. Dimakopoulos,L. Palios and A.S. Poulakidas, On the Hamiltonicityofthe Cartesian Product, available online: http://paragroup.cs.uoi.gr/Publications/120ipl2005.pdf (accessed October 2012).

M.N. Ellingham, J.D. Horton, Non-Hamiltonian 3-connected Cubic Bipartite Graphs, J. of Comb. Theory B, 34(3)(1983), 350–353. DOI: https://doi.org/10.1016/0095-8956(83)90046-1

R.M. Figueroa-Centeno, R. Ichishima and F.A. Muntaner-Batle, The place of super edge-magic labelings among other classes of labelings, Discrete Math., 231(2001), 153–168 DOI: https://doi.org/10.1016/S0012-365X(00)00314-9

M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979.

R. Gould, Advances on the HamiltonianProblem, A Survey, Graphs and Combinatorics, 19(2003), 7–52. DOI: https://doi.org/10.1007/s00373-002-0492-x

D. Holton and R.E.L. Aldred, Planar Graphs, Regular Graphs, Bipartite Graphs and Hamiltonicity, Australasian J. of Combinatorics, 20(1999), 111–131.

A. Itai, C.H. Papadimitriou and J.L. Szwarcfiter. Hamilton paths in grid graphs. SIAM Journal on Computing, 11(4)(1982),676–686 DOI: https://doi.org/10.1137/0211056

R.M. Karp, Reducibility among combinatorial problems, Complexity of Computer Computations, (1972) 85–103. DOI: https://doi.org/10.1007/978-1-4684-2001-2_9

T.P. Kirkman, On the representation of polyhedra, Phil. Trans. Royal Soc., 146(1856), 413–418. DOI: https://doi.org/10.1098/rstl.1856.0019

J. Moon and L. Moser, On Hamiltonian bipartite graphs, Israel J. of Math., 1(3)(1963), 163–165. DOI: https://doi.org/10.1007/BF02759704