Title of article
Tight bounds on maximal and maximum matchings Original Research Article
Author/Authors
Therese Biedl، نويسنده , , Erik D Demaine، نويسنده , , Christian A. Duncan، نويسنده , , Rudolf Fleischer، نويسنده , , Stephen G Kobourov، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2004
Pages
9
From page
7
To page
15
Abstract
In this paper, we study lower bounds on the size of maximal and maximum matchings in 3-connected planar graphs and graphs with bounded maximum degree. For each class, we give a lower bound on the size of matchings, and show that the bound is tight for some graph within the class.
Keywords
Matching , Bounds , Planar graphs , Bounded maximum degree
Journal title
Discrete Mathematics
Serial Year
2004
Journal title
Discrete Mathematics
Record number
948974
Link To Document