Primitive Graphs Which are Minimum Size Matching Immune
Arthur Farley, Andrzej Proskurowski
Committee:
Technical Report(May 1983)
Keywords:

This note addresses an issue concerning graphs with no disconnecting matching. A subclass of such graphs, elements of which have no subgraph with no disconnecting matching, has been investigated by Graham. He has exhibited an operation that combines two such graphs while preserving definitional property. This operation thusly defines an infinite family of these graphs. Farley and Proskurowski have defined an infinite family of graphs with no disconnecting matching which also have the minimum size among all such graphs. The two families of graphs are closely related throu£h the construction operations.