The (conditional) matching preclusion for burnt pancake graphs

被引：34
作者：
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
    AKERS, SB
    KRISHNAMURTHY, B
    [J]. IEEE TRANSACTIONS ON COMPUTERS, 1989, 38 (04) : 555 - 566
  • [2] FUNDAMENTAL ALGORITHMS FOR THE STAR AND PANCAKE INTERCONNECTION NETWORKS WITH APPLICATIONS TO COMPUTATIONAL GEOMETRY
    AKL, SG
    QIU, K
    STOJMENOVIC, I
    [J]. 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
    Cheng, Eddie
    Liptak, Laszlo
    [J]. 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
    Cheng, Eddie
    Hu, Philip
    Jia, Roger
    Liptak, Laszlo
    [J]. NETWORKS, 2012, 59 (04) : 357 - 364
  • [7] Matching preclusion and conditional matching preclusion for bipartite interconnection networks I: Sufficient conditions
    Cheng, Eddie
    Hu, Philip
    Jia, Roger
    Liptak, Laszlo
    [J]. NETWORKS, 2012, 59 (04) : 349 - 356
  • [8] Matching preclusion and conditional matching preclusion for regular interconnection networks
    Cheng, Eddie
    Lipman, Marc J.
    Liptak, Laszlo
    [J]. DISCRETE APPLIED MATHEMATICS, 2012, 160 (13-14) : 1936 - 1954
  • [9] Matching preclusion and conditional matching preclusion problems for tori and related Cartesian products
    Cheng, Eddie
    Liptak, Laszlo
    [J]. DISCRETE APPLIED MATHEMATICS, 2012, 160 (12) : 1699 - 1716
  • [10] Conditional matching preclusion for the arrangement graphs
    Cheng, Eddie
    Lipman, Marc J.
    Liptak, Laszlo
    Sherman, David
    [J]. THEORETICAL COMPUTER SCIENCE, 2011, 412 (45) : 6279 - 6289
123