Directed Hamilton Cycle Decompositions of the Tensor Products of Symmetric Digraphs

详细信息

下载全文

推荐本文 |

• 作者：P. Paulraja and S. Sivasankar
• 关键词：Tensor product ; Wreath product ; Hamilton cycle decomposition
• 刊名：Graphs and Combinatorics
• 出版时间：November, 2009
• 出版年：2009
• 期刊代码：63_0911-0119
• 类别：mat
• 卷：25
• 期：4
• 页码：571-581
• 数据来源：sp

摘要

In this paper, the existence of directed Hamilton cycle decompositions of symmetric digraphs of tensor products of regular graphs, namely, (K_r ×K_s)*, ((K_r 掳[`(K)]<sub>s</sub>) ×K<sub>n</sub>)*, ((K<sub>r</sub> ×K<sub>s</sub>) ×K<sub>m</sub>)*, ((K<sub>r</sub> 掳[`(K)]_s) ×(K_m 掳[`(K)]<sub>n</sub>))*(K_r \times K_s)^*,\,\,((K_r \circ \overline{K}_s) \times K_n)^*,\,\,((K_r \times K_s) \times K_m)^*,\,\,((K_r \circ \overline{K}_s) \times (K_m \circ \overline{K}_n))^* and (K<sub>r,r</sub> ×(K<sub>m</sub> 掳[`(K)]_n))*(K_{r,r} \times (K_m \circ \overline{K}_n))^*, where 脳 and ∘ denote the tensor product and the wreath product of graphs, respectively, are proved. In [16], Ng has obtained a partial solution to the following conjecture of Baranyai and Sz谩sz [6], see also Alspach et al. [1]: If D ₁ and D ₂ are directed Hamilton cycle decomposable digraphs, then D ₁ ∘ D ₂ is directed Hamilton cycle decomposable. Ng [17] also has proved that the complete symmetric r-partite regular digraph, K_r(s)* = (K_r 掳[`(K)]_s)*K_{r(s)}^{*} = (K_r \circ \overline{K}_s)^*, is decomposable into directed Hamilton cycles if and only if (r,s) 鹿 (4,1)(r,s) \ne (4,1) or (6, 1); using the results obtained here, we give a short proof of it, when r 脧 4,6r \notin {4,6}.