Inverse vertex covering number of a graph

Abstract

Let G = (V,E) be a graph. Let D be a minimum vertex covering of G. If V - D contains a vertex cover D? of G, then D? is called an inverse vertex cover with respect to D. The inverse vertex covering number ?0-1(G) of G is the minimum cardinality of an inverse vertex cover of G. In this paper, we initiate a study of this new parameter and establish some results on this parameter. © Taru Publications.