The graphs with maximum induced matching and maximum matching the same size

被引：34

作者：

Cameron, K ^{[1
]}

Walker, T

机构：

[1] Wilfrid Laurier Univ, Dept Math, Waterloo, ON N2L 3C5, Canada

[2] Univ Calgary, Dept Math, Calgary, AB T2N 1N4, Canada

来源：

DISCRETE MATHEMATICS | 2005年 / 299卷 / 1-3期

基金：

加拿大自然科学与工程研究理事会;

关键词：

matching; induced matching; perfect graph; optimization problems; matroid;

D O I：

10.1016/j.disc.2004.07.022

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Kobler and Rotics gave a polytime algorithm for deciding if a graph has maximum induced matching and maximum matching the same size, and for finding a maximum induced matching in a graph where equality holds. We give a simple characterization of these graphs. Our characterization provides a simpler recognition algorithm. (c) 2005 Elsevier B.V. All rights reserved.

引用

页码：49 / 55

页数：7

共 15 条

[1] 2 THEOREMS IN GRAPH THEORY [J].