k元n方体的最优条件匹配排除集

杨艳志 王世英

（山西大学 数学科学学院，山西 太原 030006）

k元n方体的最优条件匹配排除集

杨艳志 王世英

（山西大学 数学科学学院，山西 太原 030006）

设E是图G的一个边子集，若G－E中既不包含孤立点，也没有完美匹配和几乎完美匹配，则称E为G的一个条件匹配排除集.边数最少的条件匹配排除集，称为最优条件匹配排除集.文章给出了k元n方体的最优条件匹配排除集.

匹配；完美匹配；k元n方体；条件匹配排除集

0 引言

1 主要结论

［1］Wang Shiyin，Wang Ruixia，Lin Shangwei，et al.Matching preclusion fork-aryn-cubes［J］.Discrete Applied Mathematics，2010，158（18）：2 066-2 070

［2］Myung M，Bae，Bella Bose.Edge disjiont hamiltonian cycles ink-aryn-cubes and hypercubes［J］.IEEE Transactions on Computers，2003，52（10）：1 271-1 284

［3］Park Jung-Heum，Sang Hyuk Son.Conditional matching preclusion for hypercube-like interconnection networks［J］.Theoretical Computer Science，2009，410（27-29）：2 632-2 640

［4］Eddie Cheng，LászlóLipták.Matching preclusion for some Interconnection networks［J］.Networks，2007，50（2）：173-180

Optimal Conditional Matching Preclusion Sets fork-Aryn-Cubes

Yang Yanzhi Wang Shiying

（School of Mathematical Sciences，Shanxi University，Taiyuan 030006，China）

A setEof edges in graphGis called a conditional matchin g preclusion set ifG－Ehas neither isolated vertices nor perfect matching or almost perfect matching.The optimal conditional matching preclusion set is the conditional matching preclusion set with the least cardinality.In this paper，we give all optimal conditional matching preclusion sets fork-aryn-cubes.

matchings；perfect matchings；k-aryn-cubes；conditional matching preclusion sets

王映苗】

1672-2027（2011）03-0009-04

O157.5

A

2011-04-07

国家自然科学基金（61070229）.

杨艳志（1986-），男，山西吕梁石楼人，山西大学数学科学学院在读硕士研究生，主要从事图论及其应用研究.