The minimum span of \(L(2,1)\)-labelings of certain generalized Petersen graphs (Q2370433)

An \(L(2,1)\)-labeling of a graph \(G\) is a function \(f:V(G) \rightarrow \{0,1,2,\dots\}\) such that \(| f(x)-f(y)| \geq 2\) if \(d_{G}(x,y)=1\) and \(| f(x)-f(y)| \geq 1\) if \(d_{G}(x,y)=2\). The \(\lambda\)-number of \(G\) is the smallest \(k\) such that \(G\) has an \(L(2,1)\)-labeling \(f:V(G) \rightarrow \{0,1,2,\dots,k\}\). The paper focuses on \(\lambda\)-numbers of generalized Petersen graphs. (GPGs). First the \(\lambda\)-numbers of all GPGs of orders 5, 7, and 8 are determined. This settles all open cases for order \(\leq 8\). Next, a lower bound theorem of Griggs and Yeh implies that the \(\lambda\)-number of any GPG is at least 5. The authors show by construction that this bound is sharp except for orders 4, 5, 8, and 11, for which the \(\lambda\)-number \(\geq\) 6. An upper bound on the number of isomorphism classes of GPGs of any order is also calculated.