Premium
Extremal graphs having no matching cuts
Author(s) -
Bonsma Paul,
Farley Arthur M.,
Proskurowski Andrzej
Publication year - 2012
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20576
Subject(s) - combinatorics , mathematics , matching (statistics) , vertex (graph theory) , factor critical graph , graph , upper and lower bounds , discrete mathematics , line graph , voltage graph , statistics , mathematical analysis
A graph G = ( V, E ) is matching immune if there is no matching cut in G . We show that for any matching immune graph G , | E |≥⌈3(| V |−1)/2⌉. This bound is tight, as we define operations that construct, from a given vertex, exactly the class of matching immune graphs that attain the bound. © 2011 Wiley Periodicals, Inc. J Graph Theory 69:206‐222, 2012.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom