標題: Vertex-bipancyclicity of the generalized honeycomb tori
作者: Shih, Yuan-Kang
Wu, Yi-Chien
Kao, Shin-Shin
Tan, Jimmy J. M.
資訊工程學系
Department of Computer Science
關鍵字: Honeycomb torus;Pancyclic;Bipancyclic;Vertex-bipancyclic;k-vertex-bipancyclic
公開日期: 1-Dec-2008
摘要: Assume that m, n and s are integers with m >= 2, n >= 4, 0 <= s < n and s is of the same parity of m. The generalized honeycomb tori GHT(m, n, s) have been recognized as an attractive architecture to existing torus interconnection networks in parallel and distributed applications. A bipartite graph G is bipancyclic if it contains a cycle of every even length from 4 to vertical bar V(G)vertical bar inclusive. G is vertex-bipancyclic if for any vertex nu is an element of V(G), there exists a cycle of every even length from 4 to vertical bar V(G)vertical bar that passes nu. A bipartite graph G is called k-vertex-bipancyclic if every vertex lies on a cycle of every even length from k to vertical bar V(G)vertical bar. In this article, we prove that GHT(m, n, s) is 6-bipancyclic, and is bipancyclic for some special cases. Since GHT(m. n. s) is vertex-transitive, the result implies that any vertex of GHT(m. n. s) lies on a cycle of length l, where l >= 6 and is even. Besides, GHT(m, n, s) is vertex-bipancyclic in some special cases. The result is optimal in the sense that the absence of cycles of certain lengths on some GHT(m, n. s)'s is inevitable due to their hexagonal structure. (C) 2008 Elsevier Ltd. All rights reserved.
URI: http://dx.doi.org/10.1016/j.camwa.2008.07.030
http://hdl.handle.net/11536/8063
ISSN: 0898-1221
DOI: 10.1016/j.camwa.2008.07.030
期刊: COMPUTERS & MATHEMATICS WITH APPLICATIONS
Volume: 56
Issue: 11
起始頁: 2848
結束頁: 2860
Appears in Collections:Articles


Files in This Item:

  1. 000261357400010.pdf