Equimatchable Regular Graphs

被引：5

作者：

Akbari, Saieed ^{[1
]}

Ghodrati, Amir Hossein ^{[1
]}

Hosseinzadeh, Mohammad Ali ^{[2
]}

Iranmanesh, Ali ^{[2
]}

机构：

[1] Sharif Univ Technol, Dept Math Sci, Tehran, Iran

[2] Tarbiat Modares Univ, Fac Math Sci, Dept Math, Tehran, Iran

来源：

JOURNAL OF GRAPH THEORY | 2018年 / 87卷 / 01期

关键词：

equimatchable; regular graph; triangle-free graph;

D O I：

10.1002/jgt.22138

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A graph is called equimatchable if all of its maximal matchings have the same size. Kawarabayashi, Plummer, and Saito showed that the only connected equimatchable 3-regular graphs are K-4 and K-3,K- 3. We extend this result by showing that for an odd positive integer r, if G is a connected equimatchable r-regular graph, then G is an element of{Kr+1,K-r,K-r}. Also it is proved that for an even r, a connected triangle-free equimatchable r-regular graph is isomorphic to one of the graphs C-5, C-7, and K-r,K-r. (C) 2017 Wiley Periodicals, Inc.

引用

页码：35 / 45

页数：11

共 12 条

[1]

Eiben E., ARXIV150107549

[2] Equimatchable Graphs on Surfaces [J].