泡型图的条件匹配排除

王牟江山; 王镇; 王世英

您当前的位置：

首页 >

文章列表页 >

泡型图的条件匹配排除

数理科学 | 更新时间：2026-01-21

- 泡型图的条件匹配排除
- 泡型图的条件匹配排除
- 新疆大学学报（自然科学版中英文） 2011年28卷第1期页码：23-35
- 作者机构：
  
  1. 四川大学数学学院
  2. 山西大学数学科学学院
- 作者简介：
- 基金信息：
  
  国家自然科学基金资助项目(61070229)
- DOI：
  中图分类号： O157.5
- 纸质出版：2011
- 稿件说明：
移动端阅览
[1]王牟江山,王镇,王世英.泡型图的条件匹配排除[J].新疆大学学报(自然科学版),2011,28(01):23-35.

王牟江山, 王镇, 王世英. 泡型图的条件匹配排除[J]. Journal of Xinjiang University (Natural Science Edition in Chinese and English), 2011, 28(1): 23-35.
[1]王牟江山,王镇,王世英.泡型图的条件匹配排除[J].新疆大学学报(自然科学版),2011,28(01):23-35. DOI：

王牟江山, 王镇, 王世英. 泡型图的条件匹配排除[J]. Journal of Xinjiang University (Natural Science Edition in Chinese and English), 2011, 28(1): 23-35. DOI：

摘要

一个图的条件匹配排除数是最少的边的数量

使得删除这些边形成的图既没有孤立点

也没有完美匹配和几乎完美匹配.本文给出了泡型图的条件匹配排除数和它的所有最优集.

Abstract

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings.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.In this paper

we give the conditional matching preclusion number and all optimal sets for the bubble sort graphs.

关键词

Keywords

references

Brigham R C,Harary F,Violin E C,Yellen J.Perfect-matching Preclusion[J].Congressus Numerantium,2005,174:185-192.

Bondy J A,Murty U S R.Graph Theory with Applications[M].London:The Macmillan Press Ltd,1976.

王世英.一类Cayley图的边传递性和Hamilton性[J].新疆大学学报(自然科学版),1993,10(2):4-10.

Cheng E,Lesniak L,Lipman M J,Liptak L.Conditional Matching Preclusion Sets[J].Information Sciences,2009,179(8):1092-1101.

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

Aker S B,Krishnamurthy B.A Group Theoretic Model for Symmetric Interconnection Networks[J].IEEE Transaction onComputers,1989,38(4):555-566.

Cheng E,Liptak L.Matching Preclusion for Some Interconnection Networks[J].Networks,2007,50(2):173-180.

Bondy J A,Murty U S R.Graph Theory[M].New York:Springer,2007.

Curran Stephen J,Gallian Joseph A.Hamiltonian cycles and paths in Cayley graphs and digraphs-A survey[J].DiscreteMathematics,1996,156(1-3):1-18

Li T-K,Tan J J M,Hsu L-H.Hyper Hamiltonian Laceability on Edge Fault Star Graph[J].Information Science,2004,165(1-2):59-71.

Hsieh S-Y,Chen G-H,Ho C-W,Hamiltonian-laceability of Star Graphs[J].Networks,2000,36(4):225-232.

Park J-H,Son S H.Conditional Matching Preclusion for Hypercube-like Interconnection Networks[J].Theoretical ComputerScience,2009,410(27-29):2632-2640.

Wang Shiying,Wang Ruixia,Lin Shangwei,Li Jing.Matching preclusion for k-ary n-cubes[J].Discrete Applied Mathematics,2010,158(18):2066-2070.

Araki T,Kikuchi Y.Hamiltonian laceability of bubble-sort graphs with edge faults[J].Information Sciences,2007,177(13):2679-2691.

浏览量

106

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据