|
|||||
|
|
Extremal graphs having no matching cuts |
|
| Authors: | Paul Bonsma Arthur M Farley Andrzej Proskurowski |
| Institution: | 1. Department of Applied Mathematics University of Twente, The Netherlands;2. Computer Science Department University of Oregon, The Netherlands |
| Abstract: | 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 . |
| Keywords: | matching cut matching immune extremal graph primitive graph |