Sizes of Graphs with Fixed Orders and Spans for Circular-Distance-Two Labelings

Abstract

A \(k\)-circular-distance-two labeling (or \(k\)-c-labeling) of a simple graph \(G\) is a vertex-labeling, using the labels \(0, 1, 2, \ldots, k-1\), such that the “circular difference” (mod \(k\)) of the labels for adjacent vertices is at least two, and for vertices of distance-two apart is at least one. The \(\sigma\)-number, \(\sigma(G)\), of a graph \(G\) is the minimum \(k\) of a \(k\)-c-labeling of \(G\). For any given positive integers \(n\) and \(k\), let \(\mathcal {G}^{\sigma}(n, k)\) denote the set of graphs \(G\) on \(n\) vertices and \(\sigma(G) = k\). We determine the maximum size (number of edges) and the minimum size of a graph \(G \in \mathcal {G}^{\sigma}(n, k)\). Furthermore, we prove that for any value \(p\) between the maximum and the minimum size, there exists a graph \(G \in \mathcal {G}^{\sigma}(n, k)\) of size \(p\). These results are analogues of the ones by Georges and Mauro [4] on distance-two labelings.