Weak-vertex-pancyclicity of (n, k)-star graphs

详细信息	查看全文 | 推荐本文 |

• 作者：Ying-You Chen ; Dyi-Rong Duh ; Tai-Ling Ye ; Jung-Sheng Fu
• 关键词：Weak-vertex-pancyclicity ; Cycle embedding ; none ; color ; black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6V1G-4RRNXST-4&_mathId=mml19&_user=1067359&_cdi=5674&_rdoc=16&_acct=C000050221&_version=1&_userid
• 刊名：Theoretical Computer Science
• 出版年：2008
• 期刊代码：114_03043975
• 类别：cp
• 出版时间：10 May 2008
• 卷：396
• 期：1-3
• 页码：191-199
• 文件大小：705 K

摘要

The (n,k)-star graph (S_n,k for short) is an attractive alternative to the hypercube and also a generalized version of the n-star. It is isomorphic to the n-star (n-complete) graph if k=n−1 (k=1). Jwo et al. have already demonstrated in 1991 that an acc19e3" title="Click to view the MathML source" alt="Click to view the MathML source">n-star contains a cycle of every even length from 6 to n!. This work shows that every vertex in an S_n,k lies on a cycle of length l for every 3≤l≤n!/(n−k)! when 1≤k≤n−4 and n≥6. Additionally, for n−3≤k≤n−2, each vertex in an S_n,k is contained in a cycle of length ranged from 6 to n!/(n−k)!. Moreover, each constructed cycle of an available length in an S_n,k can contain a desired 1-edge.