\(L(2,1)\)-Labeling of a Circular Graph

Abstract

In this paper, the \(\lambda\)-number of the circular graph \(C(km, m)\) is shown to be at most \(9\) where \(m \geq 3\) and \(k \geq 2\), and the \(\lambda\)-number of the circular graph \(C(km + s, m)\) is shown to be at most \(15\) where \(m \geq 3\), \(k \geq 2\), and \(1 \leq s \leq m-1\). In particular, the \(\lambda\)-numbers of \(C(2m, m)\) and \(C(n, 2)\) are determined, which are at most \(8\). All our results indicate that Griggs and Yeh’s conjecture holds for circular graphs. The conjecture says that for any graph \(G\) with maximum degree \(\Delta \geq 2\), \(\lambda(G) \leq \Delta^2\). Also, we determine \(\lambda\)-numbers of \(C(n, 3)\), \(C(n, 4)\), and \(C(n, 5)\) if \(n \equiv 0 \pmod{7}\).