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

Cheng, Eddie ;

Lipman, Marc J. ;

Liptak, Laszlo .

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

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

[5] Conditional matching preclusion sets [J].

Cheng, Eddie ;

Lesniak, Linda ;

Lipman, Marc J. ;

Liptak, Laszlo .

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

[6] The (conditional) matching preclusion for burnt pancake graphs [J].

Hu, Xiaolan ;

Liu, Huiqing .

DISCRETE APPLIED MATHEMATICS, 2013, 161 (10-11) :1481-1489

[7] Matching preclusion for balanced hypercubes [J].

Lu, Huazhong ;

Li, Xianyue ;

Zhang, Heping .

THEORETICAL COMPUTER SCIENCE, 2012, 465 :10-20

[8] Matching preclusion for k-ary n-cubes [J].

Wang, Shiying ;

Wang, Ruixia ;

Lin, Shangwei ;

Li, Jing .

DISCRETE APPLIED MATHEMATICS, 2010, 158 (18) :2066-2070

[9] Hamiltonian circuit and linear array embeddings in faulty k-ary n-cubes [J].

Yang, Ming-Chien ;

Tan, Jimmy J. M. ;

Hsu, Lih-Hsing .

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2007, 67 (04) :362-368

← 1 →