## Rank numbers of graphs that are combinations of paths and cycles.(English)Zbl 1274.05143

Summary: A $$k$$-ranking of a graph $$G$$ is a function $$f:V(G)\to\{1,2,\dots,k\}$$ such that if $$f(u)=f(v)$$, then every $$u$$-$$v$$ path contains a vertex $$w$$ such that $$f(w)>f(u)$$. The rank number of $$G$$, denoted $$\chi_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 $$\chi_r(G)\leq 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.

### MSC:

 05C15 Coloring of graphs and hypergraphs 05C78 Graph labelling (graceful graphs, bandwidth, etc.) 05C38 Paths and cycles

### Keywords:

ranking; $$k$$-ranking; rank number; paths; cycles
Full Text: