Labeling outerplanar graphs with maximum degree three

DOI10.1016/J.DAM.2012.08.018MaRDI QIDQ1759878zbMATH OpenOpenAlexFDO

Authors Xiangwen Li, Sanming Zhou

Publication date 22 November 2012

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.06924

zbMATH Keywords

outerplanar graphs\(L(2,1)\)-labeling\(\lambda\)-number

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: An $L(2,1)$-labeling of a graph $G$ is an assignment of a nonnegative integer to each vertex of $G$ such that adjacent vertices receive integers that differ by at least two and vertices at distance two receive distinct integers. The span of such a labeling is the difference between the largest and smallest integers used. The $lambda$-number of $G$, denoted by $lambda(G)$, is the minimum span over all $L(2,1)$-labelings of $G$. Bodlaender {it et al.} conjectured that if $G$ is an outerplanar graph of maximum degree $Delta$, then $lambda(G)leqDelta+2$. Calamoneri and Petreschi proved that this conjecture is true when $Deltageq8$ but false when $Delta=3$. Meanwhile, they proved that $lambda(G)leqDelta+5$ for any outerplanar graph $G$ with $Delta=3$ and asked whether or not this bound is sharp. In this paper we answer this question by proving that $lambda(G)leqDelta+3$ for every outerplanar graph with maximum degree $Delta=3$. We also show that this bound $Delta+3$ can be achieved by infinitely many outerplanar graphs with $Delta=3$.

Recommendations

• Circular Distance Two Labeling and the $\lambda$-Number for Outerplanar Graphs
• scientific article; zbMATH DE number 2058562
• The \((2,1)\)-total labeling number of outerplanar graphs is at most \(\Delta + 2\)
• Some results on distance two labelling of outerplanar graphs
• scientific article; zbMATH DE number 5811532

Cited in

(11)

• Circular Distance Two Labeling and the $\lambda$-Number for Outerplanar Graphs
• Hadwiger's conjecture for squares of 2-trees
• scientific article; zbMATH DE number 5733075 (Why is no real title available?)
• scientific article; zbMATH DE number 2058562 (Why is no real title available?)
• The \(L(2,1)\)-labelling problem for cubic Cayley graphs on dihedral groups
• On zonal and inner zonal labelings of plane graphs of maximum degree 3
• L(h,1,1)-labeling of outerplanar graphs
• The minimum span of \(L(2,1)\)-labelings of generalized flowers
• Some results on distance two labelling of outerplanar graphs
• Labeling amalgamations of Cartesian products of complete graphs with a condition at distance two
• L(h,1,1)-Labeling of Outerplanar Graphs

This page was built for publication: Labeling outerplanar graphs with maximum degree three

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1759878)