期刊论文详细信息
Discussiones Mathematicae Graph Theory
Arankings of Trees
Pillone D.1 
[1] Brielle, N.J., USA;
关键词: minimal ranking;    coloring;    tree;    05c15;    05c05;   
DOI  :  10.7151/dmgt.2090
来源: DOAJ
【 摘 要 】

For a graph G = (V, E), a function f : V (G) → {1, 2, . . ., k} is a kranking for G if f(u) = f(v) implies that every u − v path contains a vertex w such that f(w) > f(u). A minimal k-ranking, f, of a graph, G, is a k-ranking with the property that decreasing the label of any vertex results in the ranking property being violated. The rank number χr(G) and the arank number ψr(G) are, respectively, the minimum and maximum value of k such that G has a minimal k-ranking. This paper establishes an upper bound for ψr of a tree and shows the bound is sharp for perfect k-ary trees.

【 授权许可】

Unknown   

  文献评价指标  
  下载次数:0次 浏览次数:0次