Circular Distance Two Labeling and the $\lambda$-Number for Outerplanar Graphs
Authors:
- Daphne Der-Fen LiuDLDaphne Der-Fen Liu
- Xuding ZhuXZXuding Zhu
- 1 January 2005
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 19 (2) , 281-293
Abstract
Let G be a graph. A circular distance two labeling with span k is a function $f: V(G) \to \{0, 1, 2, \ldots, k-1\}$ such that (1) $2 \leq |f(u)-f(v)| \leq k-2$ if u and v are adjacent and (2) $f(u) \neq f(v)$ if u and v are of distance two apart. We denote by $\lambda_c(G)$ the smallest span of a circular distance two labeling for G. Let $\Delta(G)$ be the maximum degree of G. We prove, for any outerplanar graph G with $\Delta(G) \geq 15$, $\lambda_c(G)=\Delta(G) +3$. It is also shown that there exist outerplanar graphs G with $\Delta(G) = 2, 3, 4, 5$ for which $\lambda_c(G) = \Delta(G) +4$. Moreover, we prove that $\lambda_c(G) \leq \Delta(G) +5$ for any triangulated outerplanar graph, $\lambda_c(G) \leq \Delta(G) +7$ for any outerplanar graph, and $\lambda_c(G) \leq \Delta(G) +4$ for any outerplanar graph with $\Delta(G) \geq 11$. Immediate consequences of our results include that $\lambda(G) \leq \Delta(G) + 2$ for any outerplanar graphs with $\Delta(G) \geq 15$, where $\lambda(G)$ is the minimum k of a k-L(2, 1)-labeling (or distance two labeling) for G.
Keywords
This publication has 13 references indexed in Scilit:
- Circular colorings of edge‐weighted graphsJournal of Graph Theory, 2003
- A Theorem about the Channel Assignment ProblemSIAM Journal on Discrete Mathematics, 2003
- Hamiltonicity and circular distance two labellingsDiscrete Mathematics, 2001
- Labeling Products of Complete Graphs with a Condition at Distance TwoSIAM Journal on Discrete Mathematics, 2001
- Graph labeling and radio channel assignmentJournal of Graph Theory, 1998
- The $L(2,1)$-Labeling Problem on GraphsSIAM Journal on Discrete Mathematics, 1996
- On the size of graphs labeled with a condition at distance twoJournal of Graph Theory, 1996
- Relating path coverings to vertex labellings with a condition at distance twoDiscrete Mathematics, 1994
- Labelling Graphs with a Condition at Distance 2SIAM Journal on Discrete Mathematics, 1992
- Frequency assignment: Theory and applicationsProceedings of the IEEE, 1980