期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

修正冒泡排序网络的边偶泛圈性 被引量：2

Edge-Bipancyclicity of Modified Bubble-Sort Networks
原文传递
导出
摘要 对于一个二部图G,如果在G中存在任意长为偶数l(4≤l≤|V(G)|)的圈,则称这个二部图G是偶泛圈的:如果对G中任意一边e,在G中存在任意长为偶数l(4≤l≤|V(G)|)且包含e的圈,则称这个二部图G是边偶泛圈的.修正冒泡排序网络是互连网络中的一个重要的Cayley图模型.在此,证明了对任意的自然数n,当n≥3时,修正冒泡排序网络Y_n是偶泛圈的,同时也是边偶泛圈的. A bipartite graph G is bipancyclic if G has a cycle of length l for even 4≤l≤｜V（G）｜. For a bipancyclic graph C and any edge e, C is edge-bipancyclic if e lies on a cycle of any even length l of C . Modified bubble sort networks is important networks designed form Gayleg graphs model. In this paper, we show that the modified bubble sort networks Yn is bipancyclic for n ≥ 3 and it is edge-bipancyclic for n ≥ 3.
作者 师海忠 马继勇 牛攀峰
机构地区 西北师范大学数学与信息科学学院
出处 《数学的实践与认识》 CSCD 北大核心 2011年第8期208-216,共9页 Mathematics in Practice and Theory
基金 甘肃省自然科学基金(ZS991-A25-017-G)
关键词 CAYLEY图 修正冒泡排序网络 偶泛圈 边偶泛圈 cayley graph modified bubble sort networks bipancyclicity edge-bipancyclicity
分类号 O157.5 [理学—基础数学]
  • 相关文献

参考文献3

二级参考文献11

  • 1Akers S B,Krishnamurthy B.A group-theoretic model for symmetric interconnection networks[J].IEEE Trans Computers, 1989,38 (4) : 555-565.
  • 2师海忠.关于Star-网络的一个猜想.兰州大学学报：自然科学版,2007,43:199-200.
  • 3Bondy J A,Murty U S R.Graph theory with applications[M].New York : American Elserer, 1976.
  • 4Bigs N L.Algebraic graph theory[M].Cambridge:Cambridge University Press, 1993.
  • 5Bagherzadeh N,Dowd M,Nassif N.Embedding an arbitrary tree into the star graph[J].IEEE Trans Comput,1996,45:475-481.
  • 6Day K,Tripathi A.A comparative study of topological properties of hypercubes and star graphs[J].IEEE Trans Parallel Distrib Syst, 1994,5:31-38.
  • 7Jwo J S,Lakshmivarahan S,Dhall K S.Embedding of cycles and grids in star graphs[J].J Circuits Syst Comput, 1991,1(1 ):43-74.
  • 8Hsieh S Y,Chen G H,Ho C W.longest fault-free paths in star graphs with edge fauhs[J].IEEE Trans Comput, 2001,50(9) :960- 971.
  • 9Li T K.Cycle embedding in star graphs with edg fauhs[J].Appl Math Comput,2005,167:891-900.
  • 10Xu M,Hu X D,Zhu Q.Edge-bipancyclicity of star graphs under edge-fault tolerant[J].Appl Math Comput, 2006,183 : 972-979.

共引文献19

同被引文献26

  • 1Bondy J A,Marty U S R. Graph Theory[M]. Lodon: Springer, 2008.
  • 2Cayley A. The theory of graphs, graphical representation. Mathematical Paper[J].Cambridge, 1895,10 : 26-28.
  • 3Akers S B, Krishnamurthy B. A group-theoretic model for symmetric interconnection network[J]. IEEE Transaction on Computers, 1989,38(4):555-565.
  • 4Lakshmivarahan S, Jwo J-S, Dhall S K. Syrmnetry in interconnection netwerks based on Cayley graphs of permutation groups:A survey[J]. Parallel Computing, 1993,19 : 361-407.
  • 5Araki T, Kikuchi Y. Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs[J]. Information Processing Letters, 2006,100 : 52-59.
  • 6Araki T, Kikuchi Y. Hamiltonion laceablility of bubble-sort graphs[J]. Information Sciences, 2007,177 : 2679-2691.
  • 7Shi Hai-zhong, Niu Pan-feng. Hamiltonian deconposition of some intercoonection networks[A]//Proceed of the 3th Aunnal International Conference on Combinatorial Optimization and Applications[C]. Berlin: Springer, 2009: 231-237.
  • 8Shi Hai-zhong, Niu Pan-feng, Lu Jian-bo. One conjecture of bubble sort graphs.
  • 9Li T K.Cycle embedding in star graphs with edge faults[J]. Applied Mathematics and Computation,2005,167:891-900.
  • 10Tewes M.Pancyclic in-tournaments[J].Discrete Mathemat- ics,2001,233:193-204.

引证文献2

二级引证文献7

数学的实践与认识
2011年 第8期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部