Rank numbers of graphs that are combinations of paths and cycles
Rank numbers of graphs that are combinations of paths and cycles
复制标题
对路径和循环组合的图进行排名
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Jobby Jacob
中科院分区：
文献类型：
--
作者：
Brian P. Blake;Elizabeth B Field;Jobby Jacob
图G的k-秩是函数f V V.G/！f 1; 2;：; kg使得如果f.u/D f.v/，则每条u-v路都包含一个顶点w使得f.w/ > f.u/。G的秩数记为r.G/，是使得G存在k-秩的最小k。证明了给定图G和正整数t，r.G/ t是否NP-完全的问题。然而，已经建立了许多图族的秩数。研究并建立了更多的路与圈组合图族的秩数。
A k-ranking of a graph G is a function f V V.G/!f1; 2;:::; kg such that if f.u/D f.v/, then every u-v path contains a vertexw such that f.w/ > f.u/. The rank number of G, denoted r.G/, is the minimum k such that a k-ranking exists for G. It is shown that given a graph G and a positive integer t, the question of whether r.G/ t is NP-complete. However, the rank number of numerous families of graphs have been established. We study and establish rank numbers of some more families of graphs that are combinations of paths and cycles.