Labelling of some planar graphs with a condition at distance two (Q2454996)

For positive integers \(p\) and \(q\) with \(p\geq q\) a \((p,q)\)-labelling of a graph is an assignment of nonnegative integers to the vertices of \(G\) such that adjacent vertices receive labels which differ by at least \(p\) and vertices at distance two receive labels which differ by at least \(q\). The minimum span, denoted by \(\lambda(G;p,q)\), is the smallest difference between the largest and the smallest labels taken over all \((p,q)\)-labellings of \(G\). \textit{J. van den Heuvel} and \textit{S. McGuinness} [J. Graph Theory 42, 110--124 (2003; Zbl 1008.05065)] proved that \(\lambda(G;p,q)\leq(4q-2)\Delta+10p+38q-24\) for any planar graph \(G\) with maximum degree \(\Delta\). In this paper the upper bound is improved for outerplanar graphs and for Halin graphs. For outerplanar graphs \(G\) it is proved that \(\lambda(G;p,q)\leq(2q-1)\Delta+2(2p-1)\) and for Halin graphs \(G\) that \(\lambda(G;p,q) \leq(2q-1)\Delta+6p-4q-1\).