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

一类对称群上Cayley图的最优条件匹配排除集 被引量：1

Optimally Conditional Matching Preclusion Sets for a Class of Cayley Graphs on the Symmetric Group
下载PDF
导出
摘要 图G的条件匹配排除数是最少的边的数量,使得G中存在一个这样数量的边子集F,从G中删除F中的边后形成的图既没有孤立点,也没有完美匹配或几乎完美匹配.任何一个这样的边集称为G的一个最优条件匹配排除集.条件匹配排除数是衡量网络在边故障情况下的鲁棒性的参数之一.星图和泡形图是用于大型多处理器系统的两类广受关注的互连网络.本文研究了这两类图相结合构建的一类图,给出了这类图的所有最优条件匹配排除集. The conditional matching preclusion number of a graph is the minimum number of edges, whose deletion results in a graph with no isolated vertices that has neither perfect matchings nor almost-perfect matchings. Any such optimal set is called an optimally conditional matching preclusion set. The conditional matching preclusion number is one of the parameters to measure the robustness of interconnection networks in the event of edge failure. The star graph and the bubble-sort graph are two most attractive interconnection networks of large scale multiprocessor systems. In this paper, we investigate a class of graphs which are constructed by combining the star graph with the bubble-sort graph, and give all the optimally conditional matching preclusion sets for this class of graphs.
作者 王牟江山 杨文国 王世英
机构地区 中国科学院大学数学科学学院 山西大学数学科学学院
出处 《工程数学学报》 CSCD 北大核心 2013年第6期901-910,共10页 Chinese Journal of Engineering Mathematics
基金 国家自然科学基金(71171189 61070229 61370001) 教育部博士点基金(20111401110005)~~
关键词 完美匹配 CAYLEY图 条件匹配排除 星图 泡形图 互连网络 perfect matchings Cayley graphs conditional matching preclusion star graphbubble-sort graph interconnection networks
分类号 O157.5 [理学—基础数学]
  • 相关文献

参考文献16

  • 1Brigham R C, Harary F, Violin E C, et al. Perfect-matching preclusion[J]. Congressus Numerantium, 2005, 174: 185-192.
  • 2Bondy J A, Murty U S R. Graph Theory[M]. New York: Springer, 2007.
  • 3Cheng E, Lesniak L, Lipman M J, et al. Conditional matching preclusion sets[J]. Information Sciences, 2009, 179(8): 1092-1101.
  • 4Curran S J, Gallian J A. Hamiltonian cycles and paths in Cayley graphs and digraphs—a survey [J]. Discrete Mathematics, 1996, 156(1-3): 1-18.
  • 5Cheng E, Lesniak L, Lipman M J, et ai. Matching preclusion for alternating group graphs and their generalizations [J]. International Journal of Foundations of Computer Science, 2008,19(6): 1413-1437.
  • 6Akers S B, Krishnamurthy B. A group-theoretic model for symmetric interconnection networks [J]. IEEE Transaction on Computers, 1989,38(4): 555-566.
  • 7Cheng E, Liptak L. Matching preclusion for some interconnection networks [J]. Networks, 2007, 50(2): 173-180.
  • 8Lovasz L, Plummer M D. Matching Theory[M]. New York: Elsevier Science Publishing Company, 1986.
  • 9Li K T, Tan J J M, Hsu L H. Hyper hamiltonian laceability on edge fault star graph [J]. InformationSciences, 2004,165(1-2): 59-71.
  • 10Hsieh S Y, Chen G H, Ho C W. Hamiltonian-laceability of star graphs[J]. Networks, 2000, 36(4): 225-232.

二级参考文献30

  • 1王世英.一类Cayley图的边传递性和Hamilton性[J].新疆大学学报（自然科学版）,1993,10(2):4-10. 被引量：1
  • 2Brigham R C, Harary F, Violin E C, Yellen J. Perfect-matching Preclusion[J]. CongreSsus Numerantium, 2005, 174: 185-192.
  • 3Bondy J A, Murty U S R. Graph Theory with Applications[M]. London: The Macmillan Press Ltd, 1976.
  • 4Cheng E, Lesniak L, Lipman M J,Liptak L. Conditional Matching Preclusion Sets[J]. Information Sciences, 2009, 179(8): 1092-1!01.
  • 5Cheng E, Lesniak L, Lipman M J, Liptak L. Matching preclusion for alternating group graphs and their generalizations[J]. International Journal of Foundations of Computer Science, 2008, 19(6): 1413-1437.
  • 6Aker S B, Krishnamurthy B. A Group Theoretic Model for Symmetric Interconnection Networks[J]. IEEE Transaction on Computers, 1989, 38(4): 555-566.
  • 7Cheng E, Liptak L. Matching Preclusion for Some Interconnection Networks[J]. Networks, 2007, 50(2): 173-180.
  • 8Bondy J A, Murty U S R. Graph Theory[M]. New York: Springer, 2007.
  • 9Curran Stephen J, Gallian Joseph A. Hamiltonian cycles and pb.ths in Cayley graphs and digraphs - A survey[J]. Discrete Mathematics, 1996, 156 (1-3): 1-18.
  • 10Li T-K, Tan J J M, Hsu L-H. Hyper Hamiltonian Lazeability on Edge Fault Star Graph[J]. Information Science, 2004, 165(1-2): 59-71.

共引文献3

同被引文献12

  • 1严谦泰,张忠辅.一类正则二部图的邻强边染色[J].河南师范大学学报（自然科学版）,2006,34(3):12-13. 被引量：4
  • 2Buhler J,Butler S,Graham R,et al.Hypercube orientations with only two in-degrees[J].Journal of Combinatorial Theory,Series A,2011,118(6):1695-1702.
  • 3Butler S,Hajiaghayi M T,Kleinberg R D,et al.Hat guessing games[J].SIAM Journal on Discrete Mathematics,2008,22(2):592-605.
  • 4Hungerford T W.Algebra[M].New York:Springer-Verlag,1974.
  • 5Akers S B,Krishnamurthy B.A group-theoretic model for symmetric interconnection networks[J].IEEE Transaction onComputers,1989,38(4):555-566.
  • 6Walker D,Latifi S.Improving bounds on link failure tolerance of the star graph[J].Information Sciences,2010,180(13):2571-2575.
  • 7Tsai P Y,Fu J S,Chen G H.Fault-free longest paths in star networks with conditional link faults[J].Theoretical Computer Science,2009,410(8-10):766-775.
  • 8Yang Y X,Wang S Y.Conditional connectivity of star graph networks under embedding restriction[J].Information Sciences,2012,199(15):187-192.
  • 9Bondy J A,Murty U S R.Graph Theory[M].New York:Springer,2008.
  • 10Hakimi S L.On the degrees of the vertices of a directed graph[J].Journal of The Franklin Institute,1965,279:290-308.

引证文献1

工程数学学报
2013年 第6期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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