Distance-two labelings of digraphs (Q881579): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2149737407 / rank | |||
Normal rank |
Revision as of 20:14, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Distance-two labelings of digraphs |
scientific article |
Statements
Distance-two labelings of digraphs (English)
0 references
30 May 2007
0 references
Let \(D\) be a digraph and let \(j\geq k>0\) be integers. An \(L(j,k)\)-labeling of \(D\) is a function from \(V(D)\) to the set of nonnegative integers such that for all \(x,y\in V(D)\), (i) if \(y\) is at distance one from \(x\), then \(| f(x)-f(y)| \geq j\); and (ii) if \(y\) is at distance two from \(x\), then \(| f(x)-f(y)| \geq k\). The value \(f(x)\) is called the label of \(x\) (given by \(f\)). If \(f\) is an \(L(j,k)\)-labeling of \(D\), let \(m_{j,k}(f)\) be the maximum of the labels given by \(f\). The number \(\vec{\lambda}_{j,k}(D)\) is defined as the minimum of the numbers \(m_{j,k}(f)\) for all the \(L(j,k)\)-labelings of \(D\). The authors show the following properties of the numbers \(\vec{\lambda}_{j,k}(D)\), where \(\ell(D)\) denotes the length of the longest dipath in \(D\). (1) If \(\ell(D)=2\) and \(D\) is bipartite, then \(\vec{\lambda}_{j,k}(D)=j+k\); (2) if \(\ell(D)=2\) and \(D\) is not bipartite, then \(\vec{\lambda}_{j,k}(D)=2j\); (3) if \(\ell(D)=3\) and \(D\) is bipartite, then \(j+k\leq \vec{\lambda}_{j,k}(D)=j+2k\); (4) if \(T\) is a ditree, then \(\vec{\lambda}_{j,k}(T)\leq\min\{2j, j+2k\}\), and the equality holds if \(\ell(D)=4\). Finally, the authors present a linear-time algorithm for determining \(\vec{\lambda}_{j,k}(T)\) if \(T\) is a ditree with \(\ell(T)=3\).
0 references
\(L(j,k)\)-labeling
0 references
digraph, ditree, homomorphism
0 references
algorithm
0 references