A note on collections of graphs with non-surjective lambda labelings (Q1765378): Difference between revisions

An \(L(2,\, 1)\)-labeling of a graph \(G\) is an assignment of labels from \(\{0,1,\dots,\lambda\}\) to the vertices of \(G\) such that vertices at distance two get different labels and adjacent vertices get labels that are at least two apart. The \(\lambda\)-number of \(G\) is the minimum value \(\lambda\), such that \(G\) admits an \(L(2,\, 1)\)-labeling. The authors show that the collection of connected graphs with fixed maximum degree and fixed \(\lambda\)-number such that no \(\lambda\)-labeling of the graph is surjective is infinite. Connected graphs of arbitrarily large order with maximum degree 3, \(\lambda\)-number 5 and no surjective \(\lambda\)-labelings are constructed.