On critical trees labeled with a condition at distance two (Q556846): Difference between revisions

Let \(G\) be a graph, and \(\lambda (G)\) be the smallest \(k\) so that there is a labeling of vertices of \(G\) that uses numbers in the set \( \{0,1,\dots,k\}\) with the property that adjacent vertices get integers at least two apart and vertices at distance two get distinct labels. This labeling was introduced by \textit{J. R. Griggs} and \textit{R. K. Yeh} [SIAM J. Discrete Math. 5, 586--595 (1992; Zbl 0767.05080)] where they conjectured that \(\lambda (G)\leq \Delta ^{2},\) \(\Delta \) being the maximum degree of \(G.\) A graph \(G\) is called \( \lambda \)-critical if \(\lambda (G)>\lambda (G-e)\) for each edge \(e\) of \(G\). In the paper structural properties of \(\lambda \)-critical trees with \(\Delta \geq 4\) are studied.