Vertex Ranking of Graphs
Date Issued
2007
Date
2007
Author(s)
Teng, Nancy N.H.
DOI
en-US
Abstract
A vertex ranking of a graph G is a mapping f from V(G) to the set of all natural numbers such that for any path between two distinct vertices u and v with f(u)=f(v) there is a vertex w in the path with f(w)>f(u). In this definition, we call the value f(v) the rank of the vertex v. A vertex ranking of G is optimal if the largest rank assigned is the smallest in value among all vertex rankings of G. The vertex ranking number r(G) is the
largest rank used in an optimal vertex ranking. The vertex ranking problem is to determine the vertex ranking number r(G) of a given graph G. The edge ranking problem can be defined analogously except that the mapping f is now from the edge set to the set of all nature numbers.
In the literature, vertex ranking numbers are determined for paths, cycles and cographs. There are also polynomial-time algorithms for the vertex ranking problem and the edge ranking problem [2,9,4]on trees. In this thesis, we
give a simple proof for the correctness of the algorithm for the vertex ranking on trees. We also propose an algorithm which gives an optimal vertex ranking of a block graph. Finally, we establish results for the vertex ranking problem on cacti.
Subjects
排序
ranking
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-96-R94221021-1.pdf
Size
23.53 KB
Format
Adobe PDF
Checksum
(MD5):fae210c323cf6a8c46ce6a03289e4ea8