Bipancyclic properties of Cayley graphs generated by transpositions
Bipancyclic properties of Cayley graphs generated by transpositions
复制标题
DOI：
10.1016/j.disc.2009.09.002
复制
发表时间：
2010-02
期刊：
影响因子：
--
通讯作者：
Yuuki Tanaka;Yosuke Kikuchi;Toru Araki;Y. Shibata
中科院分区：
文献类型：
--
作者：
Yuuki Tanaka;Yosuke Kikuchi;Toru Araki;Y. Shibata
循环是最基本的图类之一。对于给定的图，在图中找到不同长度的循环作为子图是很有趣的。对称群上的凯莱图Cay(Sn,S)对于作为互连网络的凯莱图的研究具有重要作用。在本文中，我们证明由转置集生成的凯莱图是顶点双环的当且仅当它不是星图时。我们还提供了 Cay(Sn,S) 是边双全环的充要条件。
Cycle is one of the most fundamental graph classes. For a given graph, it is interesting to find cycles of various lengths as subgraphs in the graph. The Cayley graph Cay(Sn,S) on the symmetric group has an important role for the study of Cayley graphs as interconnection networks. In this paper, we show that the Cayley graph generated by a transposition set is vertex-bipancyclic if and only if it is not the star graph. We also provide a necessary and sufficient condition for Cay(Sn,S) to be edge-bipancyclic.