CONDITIONAL MATCHING PRECLUSION FOR (n, k)-STAR GRAPHS

被引：3

作者：

Cheng, Eddie ^{[1
]}

Liptak, Laszlo ^{[1
]}

机构：

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

来源：

PARALLEL PROCESSING LETTERS | 2013年 / 23卷 / 01期

关键词：

Interconnection networks; perfect matchings; (n; k)-star graphs;

D O I：

10.1142/S0129626413500047

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

The matching preclusion number of an even graph G, denoted by mp(G), is the minimum number of edges whose deletion leaves the resulting graph without perfect matchings. The conditional matching preclusion number of an even graph G, denoted by mp1(G), is the minimum number of edges whose deletion leaves the resulting graph with neither perfect matchings nor isolated vertices. The class of (n,k)-star graphs is a popular class of interconnection networks for which the matching preclusion number and the classification of the corresponding optimal solutions were known. However, the conditional version of this problem was open. In this paper, we determine the conditional matching preclusion for (n,k)-star graphs as well as classify the corresponding optimal solutions via several new results. In addition, an alternate proof of the results on the matching preclusion problem will also be given.

引用

页数：13

共 14 条

[1]

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

[2]

Brigham RC., 2005, C NUMER, V174, P185

[3]

Cheng E., 2002, J INTERCONNECT NETW, V3, P19

[4]

Cheng E., 2013, TECHNICAL REPORT

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

Cheng, Eddie ;

Liptak, Laszlo .

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

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

Cheng, Eddie ;

Hu, Philip ;

Jia, Roger ;

Liptak, Laszlo .

NETWORKS, 2012, 59 (04) :357-364

[7] Matching preclusion and conditional matching preclusion for regular interconnection networks [J].

Cheng, Eddie ;

Lipman, Marc J. ;

Liptak, Laszlo .

DISCRETE APPLIED MATHEMATICS, 2012, 160 (13-14) :1936-1954

[8] Conditional matching preclusion sets [J].

Cheng, Eddie ;

Lesniak, Linda ;

Lipman, Marc J. ;

Liptak, Laszlo .

INFORMATION SCIENCES, 2009, 179 (08) :1092-1101

[9] MATCHING PRECLUSION FOR ALTERNATING GROUP GRAPHS AND THEIR GENERALIZATIONS [J].

Cheng, Eddie ;

Lesniak, Linda ;

Lipman, Marc J. ;

Liptak, Laszlo .

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2008, 19 (06) :1413-1437

[10] THE (N,K)-STAR GRAPH - A GENERALIZED STAR GRAPH [J].

CHIANG, WK ;

CHEN, RJ .

INFORMATION PROCESSING LETTERS, 1995, 56 (05) :259-264

← 1 2 →