On vertex ranking of a starlike graph |
| |
Authors: | Sun-yuan Hsieh |
| |
Affiliation: | Department of Computer Science and Information Engineering, National Chi Nai University, 1 University Rd., Puli, Nantou Hsien, Taiwan 545 |
| |
Abstract: | A vertex coloring c:V→{1,2,…,t} of a graph G=(V,E) is a vertex t-ranking if for any two vertices of the same color every path between them contains a vertex of larger color. The vertex ranking number χr(G) is the smallest value of t such that G has a vertex t-ranking. A χr(G)-ranking of G is said to be an optimal vertex ranking. In this paper, we present an O(|V|+|E|) time algorithm for finding an optimal vertex ranking of a starlike graph G=(V,E). Our result implies that an optimal vertex ranking of a split graph can be computed in linear time. |
| |
Keywords: | Algorithms Vertex ranking Starlike graphs Split graphs |
本文献已被 ScienceDirect 等数据库收录! |
|