Circulant Distant Two Labeling and Circular Chromatic Number

Abstract

Let $G$ be a graph and $d,d^{\prime }$ be positive integers, $d^{\prime }\ge d$. An $m$-$(d,d^{\prime })$-circular distance two labeling is a function $f$ from $V(G)$ to $\{0,1,2,\dots ,m-1\}$ such that:$|f(u)–f(v){|}_m\ge d$ if $u$ and $v$ are adjacent; and $|f(u)–f(v){|}_m\ge d^{\prime }$ 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^{\prime })$-circular labeling for $G$ is called the ${\sigma }_{d,d^{\prime }}$-number of $G$ and denoted by ${\sigma }_{d,d^{\prime }}(G)$. The ${\sigma }_{d,d^{\prime }}$-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.