组合星图中包含条件边错的圈的嵌入问题

广东工业大学学报 ›› 2012, Vol. 29 ›› Issue (1): 69-73.

组合星图中包含条件边错的圈的嵌入问题

广东工业大学应用数学学院，广东广州 510520

出版日期:2012-03-25 发布日期:2012-03-25
作者简介:朱大莺（1985-），女，硕士研究生，主要研究方向为组合网络理论.

Ring Embedding in (n,n2)Star Graphs with Conditional Edge Faults Conditional Edge Faults

Faculty of Applied Mathematics，Guangdong University of Technology，Guangzhou 510520，China

Online:2012-03-25 Published:2012-03-25

摘要/Abstract

摘要：
借用星图中解决包含错误边的圈的嵌入问题的思想,将其应用到组合星图中,解决组合星图中包含条件边错的圈的嵌入问题.应用数学归纳法分两种情况证明当错误边的数目f|=1时，对于组合星图Sn,n－2（n≥4）中任意一条健康边存在通过此边的所有长度从7到n!2－1的不含错误边的圈




关键词: 组合星图；星图；嵌入；同构；圈

Abstract: It presents the ideas of cycle embedding in star graphs with conditional edge faults to solve the same problem in (n,k)star graphs. This problem can be solved in two ways to prove that the length of faultfree rings in Sn,n－2 ranges from 7 to n!2－1, with |f|=1 and （n≥4）.Moreover, each cycle of the available length in an can contain a desired 1edge.

Key words: (n, k)star graph; star graph; embedding；isomorphic；cycle

朱大莺，尹志敏. 组合星图中包含条件边错的圈的嵌入问题[J]. 广东工业大学学报, 2012, 29(1): 69-73.

Zhu Daying，Yin Zhimin. Ring Embedding in (n,n2)Star Graphs with Conditional Edge Faults Conditional Edge Faults[J]. Journal of Guangdong University of Technology, 2012, 29(1): 69-73.

参考文献

［1］徐俊明.组合网络理论［M］.北京：科学出版社，2007.

［2］ Yang MingChien.Cycle embedding in star graphs with conditional edge faults［J］. Applied Mathematics and computation,2010,215:3541-3546.

［3］ Eddie,Jerrold W. Distance formula and shortest paths for the (n,k)star graphs［J］. Information Sciences,2010,180: 1671-1680.

［4］ Lin T C,DyiRongDuh.Constructing vertexdisjoint paths in (n,k)star graphs［J］.Information Sciences,2008,178:788-801.

［5］ Xiang Y H ,Stewart Iain A.Onetomany nodedisjoint paths in (n,k)star graphs［J］. Discret Applied Mathematics ,2010,158:32-70. 

［6］ Li TsengKuei , Tan Jimmy J M,Hsu LihHsing . Hyper hamiltonian laceability on edge fault star graph［J］. Information Sciences,2004,165: 59-71. 

［7］ Hsieh S Y, Chen G H, Ho C W. Longest faultfree paths in Star graphs with edge faults［J］. IEEE Trans. Comput,2001,50: 960-971.

［8］ Chen Y Y, Duh D R, Ye T L, et al. Weakvertexpancyclicity of (n,k)star graphs［J］. Theoretical Computer Science,2008,396: 191-199.

［9］ Chiang W K, Chen R J.The (n,k)star graph:An generalized star graph［J］.Information Processing Letters,1995,56:259-264.

［10］Chiang W K, Chen R J.Topogical properties of the (n,k)star graph［J］.International Journal of Foundations of Science,1998,9:235-248.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed