Computation of the vertex covering number of a graph, each block of which is a complete graph or a complete bipartite graph or a wheel or a power of a cycle or a power of a path

Abstract

We consider the well-known problem of finding the vertex covering number of a graph. It is known that this problem is NP-hard. In this paper, we give an efficient algorithm for finding the vertex covering number for connected graphs whose blocks are either complete graphs or complete bipartite graphs or wheels or powers of cycles or powers of paths.