Circulant Distant Two Labeling and Circular Chromatic Number

Abstract

Let \(G\) be a graph and \(d, d’\) be positive integers, \(d’ \geq d\). An \(m\)-\((d, d’)\)-circular distance two labeling is a function \(f\) from \(V(G)\) to \(\{0, 1, 2, \ldots, m-1\}\) such that:\(|f(u) – f(v)|_m \geq d\) if \(u\) and \(v\) are adjacent; and \(|f(u) – f(v)|_m \geq d’\) if \(u\) and \(v\) are distance two apart, where \(|x|_m := \min\{|x|, m – |x|\}\) .The minimum \(m\) such that there exists an \(m\)-\((d, d’)\)-circular labeling for \(G\) is called the \(\sigma_{d, d’}\)-number of \(G\) and denoted by \(\sigma_{d, d’}(G)\). The \(\sigma_{d, d’}\)-numbers for trees can be obtained by a first-fit algorithm. In this article, we completely determine the \(\sigma_{d, 1}\)-numbers for cycles. In addition, we show connections between generalized circular distance labeling and circular chromatic number.