Mutually independent Hamiltonianicity of Cartesian product graphs

详细信息    查看全文

• 作者：Kai-Siou Wu ; Yi-Chun Wang ; Justie Su-Tzu Juan
• 关键词：Hamiltonian ; Mutually independent ; Hamiltonianicity ; Cartesian product
• 刊名：The Journal of Supercomputing
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：73
• 期：2
• 页码：837-865
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Programming Languages, Compilers, Interpreters; Processor Architectures; Computer Science, general;
• 出版者：Springer US
• ISSN：1573-0484
• 卷排序：73

文摘

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.