$L(1,1)-$ Labeling of Direct Product of Cycles

Abstract

An $L(1,1)$-labeling of a graph $G$ is an assignment of labels from $\{0,1\cdots ,k\}$ to the vertices of $G$ such that two vertices that are adjacent or have a common neighbor receive distinct labels. The ${\lambda }_1^1-$ number, ${\lambda }_1^1(G)$ of $G$ is the minimum value $k$ such that $G$ admits an $L(1,1)$ labeling. We establish the ${\lambda }_1^1-$ numbers for direct product of cycles $C_m\times C_n$ for all positive $m,n\ge 3$, where both $m,n$ are even or when one of them is even and the other odd.

arXiv comment17 pages, 13 figures