Linear and cyclic distance-three labellings of trees

DOI10.1016/J.DAM.2014.06.003MaRDI QIDQ741540zbMATH OpenOpenAlexFDO

Authors D. Kharzeev

Publication date 12 September 2014

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

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

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)

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$.

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

Cites work

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

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
• \(L(2,1,1)\)-labeling is NP-complete for trees
• Radio number for the Cartesian product of two trees
• scientific article; zbMATH DE number 2044507 (Why is no real title available?)
• Distance labellings of Cayley graphs of semigroups
• Dispersed graph labellings
• 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)