\text { Surjective } L(3,1) \text {-labeling of circular-arc graphs }

Abstract

One of the important topics in the field of graph theory is graph labeling. $L(3,1)$-labeling problem has been widely studied in the last four decades due to its wide applications, specially in frequency assignment in mobile communication system, circuit design, radar, X-ray crystallography, coding theory, etc. Distance two surjective labeling is the surjective labeling satisfying the condition at distance one and two. Surjective $L(3,1)$-labeling is a distance two surjective labeling, which is now becomes a well studied problem. Motivated from the $L(3,1)$ labeling problem and the importance of surjective $L(3,1)$-labeling problem, we consider surjective $L(3,1)$-labeling problem for circular-arc graph $(C A G)$, where $C A G$ is a very important subclass of intersection graph. A surjective $L(3,1)$-labeling of a graph $G=(V, E)$ is a function $\vartheta$ from the node set $V(G)$ to the set of positive integers such that $|\vartheta(u)-\vartheta(v)| \geq 3$ if $d(u, v)=1$ and $|\vartheta(u)-\vartheta(v)| \geq 1$ if $d(u, v)=2$, and every label $1,2, \ldots, n$ is used exactly once, where $d(u, v)$ represents the distance between the nodes $u$ and $v$ and $n$ is the number of nodes of the graph $G$. If a graph $G$ with $n$ nodes be label by surjective $L(3,1)$-labeling then the largest label used is obviously equal to $n$.
In this article, it is shown that for any CAG $G$ with $n$ nodes and degree $\Delta>2$ can be surjectively labeled using $L(3,1)$-labeling if $n=5 \Delta-2$. Also, efficient algorithms are designed to label a $C A G$ by surjective $L(3,1)$-labeling. This is the first result for the problems on CAGs.