k元n方體的最優(yōu)條件匹配排除集

楊艷志 王世英

（山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，山西 太原 030006）

k元n方體的最優(yōu)條件匹配排除集

楊艷志 王世英

（山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，山西 太原 030006）

設(shè)E是圖G的一個邊子集，若G－E中既不包含孤立點，也沒有完美匹配和幾乎完美匹配，則稱E為G的一個條件匹配排除集.邊數(shù)最少的條件匹配排除集，稱為最優(yōu)條件匹配排除集.文章給出了k元n方體的最優(yōu)條件匹配排除集.

匹配；完美匹配；k元n方體；條件匹配排除集

0 引言

1 主要結(jié)論

［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

國家自然科學(xué)基金（61070229）.

楊艷志（1986-），男，山西呂梁石樓人，山西大學(xué)數(shù)學(xué)科學(xué)學(xué)院在讀碩士研究生，主要從事圖論及其應(yīng)用研究.