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

对称群上Cayley图的条件匹配排除数 被引量：2

Conditional Matching Preclusion Number for the Cayley Graph on the Symmetric Group
原文传递
导出
摘要 一个图的条件匹配排除数是最少的边的数量,使得从图中删除这些边后形成的图既没有孤立点,也没有完美匹配和几乎完美匹配.条件匹配排除数是衡量网络在边故障情况下的鲁棒性的参数之一.本文给出了对称群上Cayley图的条件匹配排除数. 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. The conditional matching preclusion number is one of the parameters to measure the robustness of interconnection networks in the event of edge failure. In this paper, we give the conditional matching preclusion number for the Cayley graph on the symmetric group.
作者 王牟江山 杨文国 王世英
机构地区 中国科学院大学数学科学学院 山西大学数学科学学院
出处 《应用数学学报》 CSCD 北大核心 2013年第5期813-820,共8页 Acta Mathematicae Applicatae Sinica
基金 国家自然科学基金(71171189 61370001 61070229) 教育部博士点基金(博导类)资助项目(20111401110005)
关键词 完美匹配 CAYLEY图 条件匹配排除 perfect matchings Cayley graphs conditional matching preclusion
分类号 O157.5 [理学—基础数学]
  • 相关文献

参考文献16

  • 1Cheng Eddie, Lesniak Linda Lipman Marc J, Liptgk Lszl6. Conditional Matching Preclusion Sets. Information Sciences, 2009, 179(8): 1092-1101.
  • 2Brigham R C, Harary F, Violin E C, Yellen J. Perfect-matching Preclusion. Congressus Numerantium, 2005, 174:185-192.
  • 3Bondy J A, Murty U S R. Graph Theory. New York: Springer-Verlag, 2007.
  • 4Curran Stephen J, Gallian Joseph A. Hamiltonian Cycles and Paths in Cayley Graphs and Digraphs-a Survey. Discrete Mathematics, 1996, 156(1-3): 1-18.
  • 5Cheng Eddie, Lesniak Linda, Lipman Marc J, Liptk Lszl6. Matching Preclusion for Alternating Group Graphs and their Generalizations. International Journal of Foundations of Computer Science, 2008, 19(6): 1413-1437.
  • 6Cheng Eddie, Liptk Lkszl6. Matching Preclusion for Some Interconnection Networks. Networks, 2007, 50(2): 173-180.
  • 7Li Tseng-Kuei, Tan Jimmy J.M, Hsu Lih-Hsing. Hyper Hamiltonian Laceability on Edge Fault Star Graph. Infor*mation Science, 2004, 165(1-2): 59-71.
  • 8Hsieh Sun-Yuan, Chen Gen-Huey, Ho Chin-Wen. Hamiltonian-laceability of Star Graphs. Networks, 2000, 36(4): 225-232.
  • 9Park Jung-Heum, Son Sang Hyuk. Conditional Matching Preclusion for Hypercube-like Interconnec- tion Networks. Theoretical Computer Science, 2009, 410(27-29): 2632-2640.
  • 10Wang Shiying, Wang Ruixia, Lin Shangwei, Li Jing. Matching Preclusion for k-ary n-cubes. Discrete Applied Mathematics, 2010, 158(18): 2066-2070.

二级参考文献14

  • 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.

共引文献2

同被引文献27

  • 1严谦泰,张忠辅.一类正则二部图的邻强边染色[J].河南师范大学学报（自然科学版）,2006,34(3):12-13. 被引量：4
  • 2Brigham R C, Harary F, Violin E C, et al. Perfect-matching preclusion[J]. Congressus Numerantium, 2005, 174: 185-192.
  • 3Bondy J A, Murty U S R. Graph Theory[M]. New York: Springer, 2007.
  • 4Cheng E, Lesniak L, Lipman M J, et al. Conditional matching preclusion sets[J]. Information Sciences, 2009, 179(8): 1092-1101.
  • 5Curran 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.
  • 6Cheng 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.
  • 7Akers S B, Krishnamurthy B. A group-theoretic model for symmetric interconnection networks [J]. IEEE Transaction on Computers, 1989,38(4): 555-566.
  • 8Cheng E, Liptak L. Matching preclusion for some interconnection networks [J]. Networks, 2007, 50(2): 173-180.
  • 9Lovasz L, Plummer M D. Matching Theory[M]. New York: Elsevier Science Publishing Company, 1986.
  • 10Li 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.

引证文献2

二级引证文献1

应用数学学报
2013年 第5期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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