On vertex ranking of a starlike graph

研究成果: Article同行評審

14 引文 斯高帕斯(Scopus)

摘要

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.

原文English
頁(從 - 到)131-135
頁數5
期刊Information Processing Letters
82
發行號3
DOIs
出版狀態Published - 2002 五月 16

All Science Journal Classification (ASJC) codes

  • 理論電腦科學
  • 訊號處理
  • 資訊系統
  • 電腦科學應用

指紋

深入研究「On vertex ranking of a starlike graph」主題。共同形成了獨特的指紋。

引用此