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

Blake, Brianna; Field, Elizabeth; Jacob, Jobby

Involve 6, No. 3, 369-381 (2013).

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