Linear and cyclic distance-three labellings of trees

DOI10.1016/J.DAM.2014.06.003zbMATH Open1297.05204arXiv1309.1545OpenAlexW2093421838MaRDI QIDQ741540FDOQ741540

Authors: D. Kharzeev 

Publication date: 12 September 2014

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

Abstract: Given a finite or infinite graph $G$ and positive integers $ell,h_1,h_2,h_3$, an $L(h_1,h_2,h_3)$-labelling of $G$ with span $ell$ is a mapping $f:V(G)ightarrow0,1,2,ldots,ell$ such that, for $i=1,2,3$ and any $u,vinV(G)$ at distance $i$ in $G$, $|f(u)-f(v)|geq{h}_i$. A $C(h_1,h_2,h_3)$-labelling of $G$ with span $ell$ is defined similarly by requiring $|f(u)-f(v){|}_{ell}ge{h}_i$ instead, where $|x{|}_{ell}=min|x|,ell-|x|$. The minimum span of an $L(h_1,h_2,h_3)$-labelling, or a $C(h_1,h_2,h_3)$-labelling, of $G$ is denoted by $lambd{a}_{h_1,h_2,h_3}(G)$, or $sigm{a}_{h_1,h_2,h_3}(G)$, respectively. Two related invariants, $lambd{a}_{h_1,h_2,h_3}^{\ast }(G)$ and $sigm{a}_{h_1,h_2,h_3}^{\ast }(G)$, are defined similarly by requiring further that for every vertex $u$ there exists an interval $I_u$ $mod(ell+1)$ or $modell$, respectively, such that the neighbours of $u$ are assigned labels from $I_u$ and $I_{v}cap{I}_w=emptyset$ for every edge $vw$ of $G$. A recent result asserts that the $L(2,1,1)$-labelling problem is NP-complete even for the class of trees. In this paper we study the $L(h,p,p)$ and $C(h,p,p)$ labelling problems for finite or infinite trees $T$ with finite maximum degree, where $hgepge1$ are integers. We give sharp bounds on $lambd{a}_{h,p,p}(T)$, $lambd{a}_{h,p,p}^{\ast }(T)$, $sigm{a}_{h,1,1}(T)$ and $sigm{a}_{h,1,1}^{\ast }(T)$, together with linear time approximation algorithms for the $L(h,p,p)$-labelling and the $C(h,1,1)$-labelling problems for finite trees. We obtain the precise values of these four invariants for a few families of trees. We give sharp bounds on $sigm{a}_{h,p,p}(T)$ and $sigm{a}_{h,p,p}^{\ast }(T)$ for trees with maximum degree $Deltaleh/p$, and as a special case we obtain that $sigm{a}_{h,1,1}(T)=sigm{a}_{h,1,1}^{\ast }(T)=2h+Delta-1$ for any tree $T$ with $Deltaleh$.

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

Recommendations

• The \(L(h,1,1)\)-labelling problem for trees
• Distance three labelings of trees
• Labeling trees with a condition at distance two
• \(L(2,1,1)\)-labeling is NP-complete for trees
• Distance Constrained Labelings of Trees

zbMATH Keywords

treechannel assignmentfrequency assignment\(\lambda\)-number\(\sigma\)-numbercomplete \(m\)-ary treecyclic labellingdistance-three labelling

Mathematics Subject Classification ID

Trees (05C05) Approximation algorithms (68W25) Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• Labelling Graphs with a Condition at Distance 2
• A distance-labelling problem for hypercubes
• \(L(h,1,1)\)-labeling of outerplanar graphs
• Distance three labelings for direct products of three complete graphs
• Graph labeling and radio channel assignment
• The $L(2,1)$-Labeling Problem on Graphs
• The \(L(h,1,1)\)-labelling problem for trees
• Title not available (Why is that?)
• On \(L(d,1)\)-labelings of graphs
• On the \(L(p,1)\)-labelling of graphs
• Title not available (Why is that?)
• Labeling Chordal Graphs: Distance Two Condition
• Labeling trees with a condition at distance two.
• Labeling trees with a condition at distance two
• Distance three labelings of trees
• On generalized Petersen graphs labeled with a condition at distance two
• Hamiltonicity and circular distance two labellings
• $L(2,1)$-Labeling of Hamiltonian graphs with Maximum Degree 3
• Griggs and Yeh's conjecture and \(L(p,1)\)-labelings
• Approximate L(δ₁,δ₂,…,δ_t)‐coloring of trees and interval graphs
• Distance-two labellings of Hamming graphs
• A channel assignment problem for optical networks modelled by Cayley graphs
• Labelling Cayley Graphs on Abelian Groups
• No-hole 2-distant colorings for Cayley graphs on finitely generated abelian groups

Cited In (12)

• \(L(p,2,1)\)-labeling of the infinite regular trees
• Distance three labelings of trees
• Distance-constrained labellings of Cartesian products of graphs
• Radio number of trees
• Radio number for the Cartesian product of two trees
• \(L(2,1,1)\)-labeling is NP-complete for trees
• Title not available (Why is that?)
• Dispersed graph labellings
• Distance labellings of Cayley graphs of semigroups
• Graph-Theoretic Concepts in Computer Science
• Radio number of trees
• Distance Constrained Labelings of Trees

This page was built for publication: Linear and cyclic distance-three labellings of trees

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