Abstract:
Extremal graphs are graphs which sit at the extremes. In simpler words for a class of
graphs which satisfy a certain property, extremal graphs are the ones which exhibit a
minimum or maximum of that property. Here, we take a look at a property which is
exhibited by any graph in general; δα ≤ ∆µ, where δ is the minimum degree of the
graph, α is the size of the maximum independent set, ∆ is the maximum degree, and
µ is the size of the maximum matching of the graph. We first look at non-regular
extremal graphs and regular extremal graphs (with degree 2 and 3) with respect to
the above property as characterized by Mohr and Rautenbach. Later we try our hand
at characterizing the regular extremal graphs using a general graph decomposition
given jointly by Edmonds and Gallai. In doing so, we obtain a new proof for Mohr
and Rautenbach’s characterization of 3-regular extremal graphs and we believe our
approach can be easily adapted to characterize k-regular extremal graphs for values
of k ≥ 3.
