Extremal Graphs with No Disconnecting Independent Vertex Set or Matching
Arthur Farley, Andrzej Proskurowski
Committee:
Technical Report(May 1980)
Keywords:

We describe classes of graphs with the minimum number of edges for a given number of vertices which have no disconnecting, independent set of vertices or edges. An independent vertex set has no adjacent pair of vertices. An independent edge set (i.e., a matching) has no pair of edges incident to the same vertex. A disconnecting set is one which, by its removal, transforms the given, connected graph into one having at least two connected components. We note a relationship to previously determined extremal graphs having certain connectivity and forbidden subgraph properties.