#### Vol. 6, No. 3, 2013

 Recent Issues
 The Journal About the Journal Subscriptions Editorial Board Editors’ Addresses Editors’ Interests Scientific Advantages Submission Guidelines Submission Form Ethics Statement Editorial Login Author Index Coming Soon Contacts ISSN: 1944-4184 (e-only) ISSN: 1944-4176 (print)
Rank numbers of graphs that are combinations of paths and cycles

### Brianna Blake, Elizabeth Field and Jobby Jacob

Vol. 6 (2013), No. 3, 369–381
##### Abstract

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

##### Keywords
ranking, $k$-ranking, rank number, paths, cycles
##### Mathematical Subject Classification 2010
Primary: 05C15, 05C78
Secondary: 05C38