Matching preclusion for augmented k-ary n-cubes

详细信息    查看全文

• 作者：Xinyuan Zhang
• 关键词：perfect matching ; augmented k ; ary n ; cubes ; (conditional) matching preclusion set/number ; O 157.5
• 刊名：Wuhan University Journal of Natural Sciences
• 出版年：2015
• 出版时间：February 2015
• 年：2015
• 卷：20
• 期：1
• 页码：15-24
• 全文大小：668 KB
• 参考文献：1. Brigham R C, Harary F, Biolin E C, / et al. Perfect-matching preclusion[J]. / Congressus Numerantium, 2005, 174: 185-92.
  2. Cheng E, Lipták L. Matching preclusion for some interconnection networks[J]. / Networks, 2007, 50(2): 173-80. CrossRef
  3. Cheng E, Lesniak L, Lipman M J, / et al. Conditional matching preclusion sets[J]. / Information Sciences, 2009, 179(8): 1092-101. CrossRef
  4. Cheng E, Jia R, Lu D. Matching preclusion and conditional matching preclusion for augmented cubes[J]. / Interconnection Networks, 2010, 11: 35-0. CrossRef
  5. Cheng E, Lipták L. Matching preclusion and conditional matching preclusion problems for tori related Cartesian products[J]. / Interconnection Networks, 2012, 160:1699-716.
  6. Park J H. Matching preclusion problem in restricted HL-graphs and recursive circulant / G(2 / m,4) [J]. / Journal of KISS, 2008, 35(2): 60-5.
  7. Park J H, Son S H. Conditional matching preclusion for hypercube-like interconnection networks[J]. / Theoretical Computer Science, 2009, 410(27-9): 2632-640. CrossRef
  8. Wang S Y, Wang R X, Lin S W, / et al. Matching preclusion for / k-ary / n-cubes[J]. / Discrete Applied Mathematics, 2010, 158: 2006-070.
  9. Bondy J A, Murty U S R. / Graph Theory[M]. Berlin, Heidelberg: Springer-Verlag, 2008.
  10. Xiang Y H, Stewart I A. Augmented / k-ary / n-cubes[J]. / Information Sciences, 2011, 181: 239-56. CrossRef
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Computer Science, general
  Physics
  Life Sciences
  Chinese Library of Science
  
• 出版者：Wuhan University, co-published with Springer
• ISSN：1993-4998

文摘

The (conditional) matching preclusion number of a graph is the minimum number of edges whose deletion leaves a resulting graph (with no isolated vertices) that has neither perfect matchings nor almost perfect matchings. In this paper, we find this number and classify all optimal sets for the augmented k -ary n-cubes with even k ?4.