An Algorithm for c-Vertex-Ranking of Starlike Graphs

A c-vertex-ranking of a graph G, for a positive integer c, is a labeling of the vertices of G with integers such that, for any label i deletion of all vertices with labels > i leaves connected components, each having at most c vertices with label i. The c-vertex-ranking problem is to find a covert ex-ranking of a graph using least number of ranks. In this paper, for any positive integer c, the authors present a linear-time algorithm for solving the c-vertex-ranking problem on a starlike graph with small central clique.