The (conditional) matching preclusion for burnt pancake graphs

被引：35

作者：

Hu, Xiaolan ^{[1
]}

Liu, Huiqing ^{[1
]}

机构：

[1] Hubei Univ, Fac Math & Comp Sci, Wuhan 430062, Peoples R China

来源：

DISCRETE APPLIED MATHEMATICS | 2013年 / 161卷 / 10-11期

关键词：

Interconnection networks; Burnt pancake graph; Perfect matching; (Conditional) matching preclusion set/number; INTERCONNECTION NETWORKS; ALGORITHM; PATHS;

D O I：

10.1016/j.dam.2013.01.010

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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, and the conditional matching preclusion number of a graph is the minimum number of edges whose deletion leaves a resulting graph with no isolated vertices that has neither perfect matchings nor almost perfect matchings. In this paper, we find these two numbers for the burnt pancake graphs and show that every optimal (conditional) matching preclusion set is trivial. (C) 2013 Elsevier B.V. All rights reserved.

引用

页码：1481 / 1489

页数：9

共 27 条

[1] A GROUP-THEORETIC MODEL FOR SYMMETRIC INTERCONNECTION NETWORKS [J].

AKERS, SB ;

KRISHNAMURTHY, B .

IEEE TRANSACTIONS ON COMPUTERS, 1989, 38 (04) :555-566

[2] FUNDAMENTAL ALGORITHMS FOR THE STAR AND PANCAKE INTERCONNECTION NETWORKS WITH APPLICATIONS TO COMPUTATIONAL GEOMETRY [J].

AKL, SG ;

QIU, K ;

STOJMENOVIC, I .

NETWORKS, 1993, 23 (04) :215-225

[3]

[Anonymous], 2007, GRAPH THEORY

[4]

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

[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 bipartite interconnection networks I: Sufficient conditions [J].

Cheng, Eddie ;

Hu, Philip ;

Jia, Roger ;

Liptak, Laszlo .

NETWORKS, 2012, 59 (04) :349-356

[8] 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

[9] Matching preclusion and conditional matching preclusion problems for tori and related Cartesian products [J].

Cheng, Eddie ;

Liptak, Laszlo .

DISCRETE APPLIED MATHEMATICS, 2012, 160 (12) :1699-1716

[10] Conditional matching preclusion for the arrangement graphs [J].

Cheng, Eddie ;

Lipman, Marc J. ;

Liptak, Laszlo ;

Sherman, David .

THEORETICAL COMPUTER SCIENCE, 2011, 412 (45) :6279-6289

← 1 2 3 →