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

From MaRDI portal
Revision as of 10:30, 27 June 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Labelling of some planar graphs with a condition at distance two
scientific article

    Statements

    Labelling of some planar graphs with a condition at distance two (English)
    0 references
    0 references
    0 references
    22 October 2007
    0 references
    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\).
    0 references
    \((p, q)\)-labelling
    0 references
    outerplanar graph
    0 references
    Halin graph
    0 references

    Identifiers