School Seminars and Colloquia

L(p,q)-labelling of Outerplanar Graphs

ORSUM Seminar

by Dr Michael Hoffmann


Institution: University of Leicester
Date: Thu 10th May 2007
Time: 1:05 PM
Location: Room 213, Richard Berry Building

Abstract: Labelling or Colouring of graphs is a wide and well studied area. We introduce a technique to compose graphs while maintaining enough
information about the labelling. This technique will be demonstrate on the
$L(p,q)$ labelling on outerplanar graphs. The results obtained do improve
previously known lower and upper bounds.

In details: An $L(p,q)$-labelling of a graph $G$ is a labelling of the
vertices by the integers, where the labels of adjacent vertices differ by $p$ and the labels of vertices at distance two differ by $q$. We will
present an algorithm that decides whether every outerplanar graph of degree
at most $\Delta$ can be $L(p,q)$-labelled with $n$ labels. We apply this
algorithm to three different labelling problems for outerplanar graphs. We give precise bounds for $L(2,1)$-labelling outerplanar graphs where $\Delta=3$ and increase the previously known lower bounds when $\Delta=4,5$
and $6$. We give precise bounds for $L(1,1)$-labelling outerplanar graphs where $\Delta=4,5$. We give a precise bound when $L(0,1)$-labelling outerplanar graphs where $\Delta=3$.

In practice precise bounds can be found for small degree $\Delta$. The challenge to understand the (possible large) counter examples remains. Their structure could give rise to improved bounds for any degree.

For More Information: Mark Fackrell: mfackrel@ms.unimelb.edu.au