Matching preclusion for k-ary n-cubes with odd k ≥ 3

被引：1

作者：

Hu, Xiaomin ^{[1
]}

Zhao, Bin ^{[2
]}

Tian, Yingzhi ^{[1
]}

Meng, Jixiang ^{[1
]}

机构：

[1] Xinjiang Univ, Coll Math & Syst Sci, Urumqi 830046, Peoples R China

[2] Hebei Univ Engn, Sch Math & Phys, Handan 056038, Peoples R China

来源：

DISCRETE APPLIED MATHEMATICS | 2017年 / 229卷

关键词：

Matching preclusion; Matchable; k-ary n-cubes;

D O I：

10.1016/j.dam.2017.06.001

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The matching preclusion number of a graph is the minimum number of edges whose deletion results the remaining graph that has neither perfect matchings nor almost perfect matchings. In this paper, we prove that the matching preclusion number of k-ary n-cubes is 4n - 1 except k = 3 and n = 2, where k is odd and k >= 3. (C) 2017 Elsevier B.V. All rights reserved.

引用

页码：90 / 100

页数：11

共 9 条

[1] [Anonymous], 2007, GRAPH THEORY
[2] Brigham R.C., 2005, Congressus Numerantium, V174, P185
[3] 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
[4] 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
[5] Conditional matching preclusion sets
Cheng, Eddie
Lesniak, Linda
Lipman, Marc J.
Liptak, Laszlo
[J]. INFORMATION SCIENCES, 2009, 179 (08) : 1092 - 1101
[6] The (conditional) matching preclusion for burnt pancake graphs
Hu, Xiaolan
Liu, Huiqing
[J]. DISCRETE APPLIED MATHEMATICS, 2013, 161 (10-11) : 1481 - 1489
[7] Matching preclusion for balanced hypercubes
Lu, Huazhong
Li, Xianyue
Zhang, Heping
[J]. THEORETICAL COMPUTER SCIENCE, 2012, 465 : 10 - 20
[8] Matching preclusion for k-ary n-cubes
Wang, Shiying
Wang, Ruixia
Lin, Shangwei
Li, Jing
[J]. DISCRETE APPLIED MATHEMATICS, 2010, 158 (18) : 2066 - 2070
[9] Hamiltonian circuit and linear array embeddings in faulty k-ary n-cubes
Yang, Ming-Chien
Tan, Jimmy J. M.
Hsu, Lih-Hsing
[J]. JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2007, 67 (04) : 362 - 368

← 1 →