On the generation of minimal graph extensions by the method of canonical representatives

A graph G* is a k-vertex (edge) extension of a graph G if every graph obtained by removing any k vertices (edges) from G* contains G. A k-vertex (edge) extension G* of graph G is said to be minimal if it contains minimum possible vertices and has the minimum number of edges among all k-vertex (edge) extension of graph G. The paper proposes an algorithm for generating all non-isomorphic minimal vertex (edge) k-extensions of a given graph with isomorphism rejection technique by using method of generating canonical representatives.

Keywords

Authors

References