×

An optimal \(k\)-ranking characterization of oriented paths and cycles. (English) Zbl 1220.05048

Summary: A \(k\)-ranking of a graph (digraph) is a coloring of the vertex set with \(k\) positive integers such that every (directed) path connecting two vertices with the same color there is a vertex with a larger label The rank number of a graph is defined to be the smallest \(k\) such that \(G\) has a minimal \(k\)-ranking. Here we present rank numbers for oriented paths and cycles. Furthermore, we give a complete characterization of oriented paths and cycles in terms of their rank number.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles
PDFBibTeX XMLCite