We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Mutually independent Hamiltonianicity of Cartesian product graphs.
- Authors
Wu, Kai-Siou; Wang, Yi-Chun; Juan, Justie
- Abstract
Two Hamiltonian cycles $$C_1=\langle u_0,u_1,u_2,...,u_{n-1},u_0 \rangle $$ and $$C_2=\langle v_0,v_1,v_2,...,v_{n-1},v_0 \rangle $$ of a graph G are independent starting at $$u_0$$ if $$u_0=v_0, u_i\ne v_i$$ for all $$1\le i\le n-1$$ . A set of Hamiltonian cycles C of G are k-mutually independent starting at vertex u if any two different Hamiltonian cycles of C are independent starting at u and $$|C| = k$$ . The mutually independent Hamiltonianicity of graph G is the maximum integer k, such that for any vertex u of G there exist k-mutually independent Hamiltonian cycles starting at u, denoted by IHC( $$G)=k$$ . The Cartesian product of graphs G and H, written by $$G \times H$$ , is the graph with vertex set $$V(G) \times V(H)$$ specified by putting ( u, v) adjacent to $$(u', v')$$ if and only if $$(1)\;u = u'$$ and $$vv' \in E(H),$$ or $$(2)\;v = v'$$ and $$uu' \in E(G)$$ . In this paper, for $$G = G_1 \times G_2$$ , where $$G_1$$ and $$G_2$$ are Hamiltonian graphs, IHC( $$G_1 \times G_2) \ge $$ IHC( $$G_1)$$ or IHC( $$G_1)$$ + 2 is proved when given some different conditions.
- Subjects
HAMILTONIAN systems; HAMILTONIAN mechanics; COMPUTING platforms; INFORMATION technology; WIRELESS communications
- Publication
Journal of Supercomputing, 2017, Vol 73, Issue 2, p837
- ISSN
0920-8542
- Publication type
Article
- DOI
10.1007/s11227-016-1804-x