Equimatchable graphs are C2k+1-free for k ≥ 4

被引：5

作者：

Dibek, Cemil ^{[1
]}

Ekim, Tinaz ^{[1
]}

Gozupek, Didem ^{[3
]}

Shalom, Mordechai ^{[1
,2
]}

机构：

[1] Bogazici Univ, Dept Ind Engn, Istanbul, Turkey

[2] TelHai Acad Coll, IL-12210 Upper Galilee, Israel

[3] Gebze Tech Univ, Dept Comp Engn, Kocaeli, Turkey

来源：

DISCRETE MATHEMATICS | 2016年 / 339卷 / 12期

关键词：

Equimatchable graph; Forbidden subgraph; Gallai-Edmonds decomposition; Factor-critical;

D O I：

10.1016/j.disc.2016.06.003

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A graph is equimatchable if all of its maximal matchings have the same size. Equimatchable graphs are extensively studied in the literature mainly from structural point of view. Here we provide the first family of forbidden subgraphs of equimatchable graphs. Since equimatchable graphs are by definition not hereditary, this task of finding forbidden subgraphs requires the use of structural results from previous works. (C) 2016 Elsevier B.V. All rights reserved.

引用

页码：2964 / 2969

页数：6

共 15 条

[1] Efficient recognition of equimatchable graphs [J].