Matching preclusion and conditional matching preclusion for bipartite interconnection networks II: Cayley graphs generated by transposition trees and hyper-stars

被引：25

作者：

Cheng, Eddie ^{[1
]}

Hu, Philip ^{[2
]}

Jia, Roger ^{[3
]}

Liptak, Laszlo ^{[1
]}

机构：

[1] Oakland Univ, Dept Math & Stat, Rochester, MI 48309 USA

[2] Yale Univ, New Haven, CT 06511 USA

[3] Univ Michigan, Ann Arbor, MI 48109 USA

来源：

NETWORKS | 2012年 / 59卷 / 04期

关键词：

interconnection networks; perfect matching; Cayley graphs; hyper-stars; MAXIMAL CONNECTED COMPONENT; FAULTY VERTICES;

D O I：

10.1002/net.20441

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

The matching preclusion number of a graph with an even number of vertices is the minimum number of edges whose deletion results in a graph that has no perfect matchings. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. It is natural to look for obstruction sets beyond those induced by a single vertex. 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 no perfect matchings. In this companion paper of Cheng et al. (Networks (NET 1554)), we find these numbers for a number of popular interconnection networks including hypercubes, star graphs, Cayley graphs generated by transposition trees and hyper-stars. (c) 2011 Wiley Periodicals, Inc. NETWORKS, 2011

引用

页码：357 / 364

页数：8

共 19 条

[1]

Akers S. B., 1987, Proceedings of the 1987 International Conference on Parallel Processing, P393

[2]

Brigham R.C., 2005, Congressus Numerantium, V174, P185

[3] Increasing the connectivity of the star graphs [J].

Cheng, E ;

Lipman, MJ .

NETWORKS, 2002, 40 (03) :165-169

[4]

Cheng E., 2006, C NUMER, V80, P65

[5]

Cheng E., NETWORKS

[6]

Cheng E., 2006, CONGR NUMER CONF J N, V180, P81

[7]

Cheng E., ARS COMBIN IN PRESS

[8]

Cheng E., 2009, TECHNICAL REPORTS SE

[9] Linearly many faults in Cayley graphs generated by transposition trees [J].

Cheng, Eddie ;

Liptak, Laszlo .

INFORMATION SCIENCES, 2007, 177 (22) :4877-4882

[10] Matching preclusion for some interconnection networks [J].

Cheng, Eddie ;

Liptak, Laszlo .

NETWORKS, 2007, 50 (02) :173-180

← 1 2 →