Matching preclusion number of graphs

被引：7

作者：

Wang, Zhao ^{[1
]}

Mao, Yaping ^{[2
,5
]}

Cheng, Eddie ^{[3
]}

Zou, Jinyu ^{[4
]}

机构：

[1] China Jiliang Univ, Coll Sci, Hangzhou 310018, Zhejiang, Peoples R China

[2] Qinghai Normal Univ, Sch Math & Stat, Xining 810008, Qinghai, Peoples R China

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

[4] Qinghai Normal Univ, Sch Comp Sci, Xining 810008, Qinghai, Peoples R China

[5] Ctr Math & Interdisciplinary Sci Qinghai Prov, Xining 810008, Qinghai, Peoples R China

来源：

THEORETICAL COMPUTER SCIENCE | 2019年 / 759卷

基金：

美国国家科学基金会;

关键词：

Interconnection networks; Perfect matching; Matching preclusion number; Nordhaus-Gaddum problem; Extremal problem;

D O I：

10.1016/j.tcs.2019.01.005

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The matching preclusion number of a graph G, denoted by mp(G), is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. In this paper, we first give some sharp upper and lower bounds of matching preclusion number. Next, graphs with large and small matching preclusion number are characterized, respectively. In the end, we investigate some extremal problems and the Nordhaus-Gaddum-type relations on matching preclusion number. (C) 2019 Elsevier B.V. All rights reserved.

引用

页码：61 / 71

页数：11

共 22 条

[1] A survey of Nordhaus-Gaddum type relations [J].

Aouchiche, Mustapha ;

Hansen, Pierre .

DISCRETE APPLIED MATHEMATICS, 2013, 161 (4-5) :466-546

[2]

BERGE C, 1958, CR HEBD ACAD SCI, V247, P258

[3]

Bondy J.A., 2008, GRAPH THEORY GTM, V244

[4]

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

[5]

Cheng E., 2010, THEORET COMPUT SCI, V576, P30

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

Cheng, Eddie ;

Liptak, Laszlo .

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

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

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

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

[10] MATCHING PRECLUSION AND CONDITIONAL MATCHING PRECLUSION FOR AUGMENTED CUBES [J].

Cheng, Eddie ;

Jia, Randy ;

Lu, David .

JOURNAL OF INTERCONNECTION NETWORKS, 2010, 11 (1-2) :35-60

← 1 2 3 →