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
Victor Lepin, Mihai Tălmaciu, О. И. Дугинов · BSU Digital Library (Belarusian State University) · 2013
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.