A Note on n-Set Distance-Labelings of Graphs

Roger K. Yeh

Department of Applied Mathematics, Feng Chia University, Taichung City.

DOI: 10.4236/ojdm.2021.113005                

Abstract

This note is considered as a sequel of Yeh [1]. Here, we present a generalized (vertex) distance labeling (labeling vertices under constraints depending the on distance between vertices) of a graph. Instead of assigning a number (label) to each vertex, we assign a set of numbers to each vertex under given conditions. Some basic results are given in the first part of the note. Then we study a particular class of this type of labelings on several classes of graphs.

Keywords

Graph Distance Labeling

1. Introduction

Inspired by a channel assignment problem proposed by Roberts [2] in 1988, Griggs and Yeh [3] formulated the L(2,1)-labeling problem for graphs. There are considerable amounts of articles studying this labeling and its generalizations or related problems. Readers can see [4] or [5] for a survey. In this note, we like to consider a generalization of the L(2,1)-labeling. Let A and B be two subsets of natural numbers. Define $\Vert A-B\Vert =\min \left\{\left|a-b\right|:a\in A,b\in B\right\}$. Denote the set

$\left[k\right]=\left\{0,1,\cdots ,k\right\}$ and $\left(\begin{array}{c}\left[k\right]\\ n\end{array}\right)$ the collection of alln-subsets of $\left[k\right]$.

Motivated by the article [6], we propose the following labeling on a graph.

Let $G=\left(V,E\right)$ be a graph and n be a positive integer. Given non-negative integers ${\delta }_1\ge {\delta }_2$ an $L^{\left(n\right)}\left({\delta }_1,{\delta }_2\right)$ -labeling is a function $f:V\left(G\right)\to \left(\begin{array}{c}\left[k\right]\\ n\end{array}\right)$ for

some $k\ge 1$ such that $\left|f\left(u\right)-f\left(v\right)\right|\ge {\delta }_i$ whenever the distance between u andv inG isi, for $i=1,2$. (The minimum value and the maximum value of ${\displaystyle {\cup }_{v\in V\left(G\right)}f\left(v\right)}$ is 0 and k, respectively.) The value kis called the span of f. The smallest k so that there is an $L^{\left(n\right)}\left({\delta }_1,{\delta }_2\right)$ -labeling f with span k, is denoted by ${\lambda }^{\left(n\right)}\left(G;{\delta }_1,{\delta }_2\right)$ and called the $L^{\left(n\right)}\left({\delta }_1,{\delta }_2\right)$ -labeling number of G. An $L^{\left(n\right)}\left({\delta }_1,{\delta }_2\right)$ -labeling with span ${\lambda }^{\left(n\right)}\left(G;{\delta }_1,{\delta }_2\right)$ is called an optimal $L^{\left(n\right)}\left({\delta }_1,{\delta }_2\right)$ -labeling. If $n=1$ then notations $L^{\left(1\right)}$ and ${\lambda }^{\left(1\right)}$ will be simplified as L and $\lambda$, respectively.

Note: 1) The elements in $\left[k\right]$ are called “numbers” and $f\left(u\right)$ is called the “label” of u. So, a label is a set in this problem. 2) Using our notation, the labeling in [6] is the $L\left({\delta }_1,0\right)$ -labeling for ${\delta }_1\ge 1$.

Previously, we have studied the $L^{\left(2\right)}\left(2,1\right)$ -labeling problem (cf. [1] ). In this note, we will first investigate properties of the $L^{\left(n\right)}\left({\delta }_1,{\delta }_2\right)$ for $n\ge 1$. Then, we study the case of $\left({\delta }_1,{\delta }_2\right)=\left(1,1\right)$.

2. Preliminarily

Let G be a graph and n an positive integer. Now, we construct a new graph $G^{\left(n\right)}$ by replacing each vertex v in G by n vertices $v_i$, $1\le i\le n$ and $u_i$ is adjacent to $v_j$ for all $i,j$, in $G^{\left(n\right)}$, whenever u and v is adjacent in G. That is, $u_i$ and $v_j$, for all $i,j$, induces a complete bipartite graph $K_{n,n}$. Note that $G^{\left(1\right)}=G$.

It is easy to verify that ${\lambda }^{\left(n\right)}\left(G;{\delta }_1,1\right)=\lambda \left(G^{\left(n\right)};{\delta }_1,1\right)$. Thus, for example, ${\lambda }^{\left(n\right)}\left(K_m;2,1\right)=\lambda \left(K_{n,n,\cdots ,n};2,1\right)=nm+m-2$, where $m\ge 2$, by previous result on complete m-partite graph $K_{n,n,\cdots ,n}$ (cf. [3] ).

Next, we consider the relation between the labeling numbers for $n=1$ and $n\ge 1$. In the following, $\lambda \left(G;1,1\right)$ and ${\lambda }^{\left(n\right)}\left(G;1,1\right)$ are denoted by ${\lambda }_1\left(G\right)$ and ${\lambda }_1^{\left(n\right)}\left(G\right)$, respectively, for short.

Proposition 2.1. Let $n\ge 1$, ${\delta }_1\ge {\delta }_2$ be nonnegative integers and Δ be the maximum degree of G. Then

1) $\left(n-1\right)\left(\Delta +1\right)+{\delta }_1+\left(\Delta -1\right){\delta }_2\le {\lambda }^{\left(n\right)}\left(G;{\delta }_1,{\delta }_1\right)$.

2) ${\lambda }^{\left(n\right)}\left(G;{\delta }_1,{\delta }_1\right)\le \lambda \left(G;n+{\delta }_1-1,n+{\delta }_2-1\right)+n-1$.

Proof.

1) A vertexu with the maximum degree Δ in a graphG is called a major vertex of G. By counting the numbers for the labels of a major vertex and its neighbors and numbers need to separate each label (the $\left({\delta }_1,{\delta }_2\right)$ condition), we shall have the trivial lower bound.

2) Let $\lambda \left(G;n+{\delta }_1-1,n+{\delta }_2-1\right)=k$ and f an optimal $L\left(n+{\delta }_1-1,n+{\delta }_2-1\right)$ -labeling. Define sets $L_i=\left\{i,i+1,\cdots ,i+n-1\right\}$, $i=0,1,\cdots ,k$ and function

$g_f:V\left(G\right)\to \left(\begin{array}{c}\left[k+n-1\right]\\ n\end{array}\right)$ by $g_f\left(u\right)=L_i$ whenever $f\left(u\right)=i$ for $i=0,1,\cdots ,k$.

Let u and v be distinct vertices with $d_G\left(u,v\right)=j$ for $j=1,2$ in G. Suppose $f\left(u\right)=i$ and $f\left(v\right)=i+n+{{\delta }^{\prime }}_j-1$ for ${{\delta }^{\prime }}_j\ge {\delta }_j$ for $j=1,2$. Then $g_f\left(u\right)=\left\{i,i+1,\cdots ,i+n-1\right\}$ and $g_f\left(v\right)=\left\{i+n+{{\delta }^{\prime }}_j-1,i+n+{{\delta }^{\prime }}_j,\cdots ,i+n+{{\delta }^{\prime }}_j-1+n-1\right\}$. Hence $\Vert g_f\left(u\right)-g_f\left(v\right)\Vert =\left(i+n+{{\delta }^{\prime }}_j\right)-\left(i+n-1\right)={{\delta }^{\prime }}_j\ge {\delta }_j$ for $j=1,2$. Thus $g_f$ is an $L^{\left(n\right)}\left({\delta }_1,{\delta }_2\right)$ -labeling with span $k+n-1$. Therefore

${\lambda }^{\left(n\right)}\left(G;{\delta }_1,{\delta }_1\right)\le \lambda \left(G;n+{\delta }_1-1,n+{\delta }_2-1\right)+n-1$. ∎

The following is the direct consequence of Proposition 2.1 when $\left({\delta }_1,{\delta }_1\right)=\left(1,1\right)$. Also notice that $\lambda \left(G;d{\delta }_1,d{\delta }_2\right)=d\lambda \left(G;{\delta }_1,{\delta }_2\right)$.

Corollary 2.2. Let Δ be the maximum degree of G. Then

$\left(\text{Δ}+1\right)n-1\le {\lambda }_1^{\left(n\right)}\left(G\right)\le n{\lambda }_1\left(G\right)+n-1$. ∎

By Corollary 2.2, we know that whenever ${\lambda }_1\left(G\right)=\Delta$, the lower bound and the upper bound are equal and hence ${\lambda }_1^{\left(n\right)}\left(G\right)=\left(\Delta +1\right)n-1$. There are several well-known classes of graphs whose ${\lambda }_1$ values are all Δ (see [7] ). For example, tree T, wheel $W_m$ (with m rims), the square lattice ${\Gamma }_S$ (4-regular infinite plane graph), the hexagonal lattice ${\Gamma }_H$ (3-regular infinite plane graph), and the triangular lattice ${\Gamma }_{\Delta }$ (6-regular infinite plane graph) are all with ${\lambda }_1=\Delta$. We summarize as follows.

Theorem 2.3.

1) ${\lambda }_1^{\left(n\right)}\left(T\right)=\left(\Delta \left(T\right)+1\right)n-1$.

2) ${\lambda }_1^{\left(n\right)}\left(W_m\right)=\left(m+1\right)n-1$.

3) ${\lambda }_1^{\left(n\right)}\left({\Gamma }_S\right)=5n-1$.

4) ${\lambda }_1^{\left(n\right)}\left({\Gamma }_H\right)=4n-1$.

5) ${\lambda }_1^{\left(n\right)}\left({\Gamma }_{\Delta }\right)=7n-1$. ∎

3. Cycles

We know that the maximum degree of a cycle C_m of order $m\ge 3$ is 2. However, ${\lambda }_1\left(C_m\right)$ is not necessary 2. It depends on m. In this section, we will consider $L^{\left(n\right)}\left(1,1\right)$ -labelings on cycles.

Proposition 3.1. Let C_m be a cycle of order $m\ge 3$. Then ${\lambda }_1^{\left(n\right)}\left(C_m\right)=3n-1$ if $m\equiv 0\left(\mathrm{mod}3\right)$.

Proof. Since the maximum degree of C_m is 2, the trivial lower bound is $3n-1$ by Corollary 2.2. On the other hand, we use $\left\{0,1,\cdots ,n-1\right\}$, $\left\{n,n+1,\cdots ,2n-1\right\}$ and $\left\{2n,2n+1,\cdots ,3n-1\right\}$ consecutively to label vertices of C_m where $m\equiv 0\left(\mathrm{mod}3\right)$, to obtain an $L^{\left(n\right)}\left(1,1\right)$ -labeling of C_m with span $3n-1$. Thus, we have the exact value of ${\lambda }_1^{\left(n\right)}\left(C_m\right)$ in this case. ∎

Lemma 3.2. Let C_m be a cycle of order m where $m\cancel{\equiv }0\left(\mathrm{mod}3\right)$. Then ${\lambda }_1^{\left(n\right)}\left(C_m\right)\ge 3n$.

Proof. Let $V\left(C_m\right)=\left\{v_1,v_2,\cdots ,v_m\right\}$ where $v_i$ is adjacent to $v_{i+1}$ for $i=1,2,\cdots ,m$ where $v_{m+1}=v_1$. Suppose ${\lambda }_1^{\left(n\right)}\left(C_m\right)\le 3n-1$. Letf be an $L^{\left(n\right)}\left(1,1\right)$ -labeling with span $3n-1$. Let $f\left(v_1\right)=A,f\left(v_2\right)=B$ and $f\left(v_3\right)=C$. Since, by definition, $f\left(v_1\right),f\left(v_2\right)$ and $f\left(v_3\right)$ are distinct, that is, $\left|A\cup B\cup C\right|=3n$ and $A\cup B\cup C=\left[3n-1\right]$. Now, $f\left(v_4\right)\cap \left(B\cup C\right)=\varnothing$ and $f\left(v_4\right)\subseteq \left[3n-1\right]$. Hence $f\left(v_4\right)=A$. Consider $f\left(v_5\right)$. Again, we have $f\left(v_5\right)\cap \left(A\cup C\right)=\varnothing$ and $f\left(v_5\right)\subseteq \left[3n-1\right]$. Hence $f\left(v_5\right)=B$. In general, we have 1) $f\left(v_i\right)=A$ if $i\equiv 1\left(\mathrm{mod}3\right)$, 2) $f\left(v_i\right)=B$ if $i\equiv 2\left(\mathrm{mod}3\right)$ and 3) $f\left(v_i\right)=C$ if $i\equiv 0\left(\mathrm{mod}3\right)$, for $i=1,2,\cdots ,m$.

If $m\equiv 1\left(\mathrm{mod}3\right)$ then $f\left(v_m\right)=A$. But $v_m$ is adjacent to $v_1$, where

$f\left(v_1\right)=A$. This violates the condition on adjacent vertices. If $m\equiv 2\left(\mathrm{mod}3\right)$ then $f\left(v_m\right)=B=f\left(v_2\right)$ while the distance between $v_m$ and $v_2$ is 2. Again, this violates the condition on distance 2 vertices. We have a contradiction on each case. Therefore, ${\lambda }_1^{\left(n\right)}\left(C_m\right)\ge 3n$ for $m\cancel{\equiv }0\left(\mathrm{mod}3\right)$. ∎

Proposition 3.3. If 1) $m\equiv 1\left(\mathrm{mod}3\right)$ and $m\ge 3n+1$ or 2) $m\equiv 2\left(\mathrm{mod}3\right)$ and $m\ge 6n+2$ then ${\lambda }_1^{\left(n\right)}\left(C_m\right)=3n$.

Proof. Let $V\left(C_m\right)=\left\{v_1,v_2,\cdots ,v_m\right\}$.

1) Suppose $m=3n+1$ and Define $A_0=\left\{0,1,\cdots ,n-1\right\}$, $A_1=\left\{n,n+1,\cdots ,2n-1\right\}$, $A_2=\left\{2n,2n+1,\cdots ,3n-1\right\}$ and $A_3=\left\{3n,0,\cdots ,n-2\right\}$. Denote $X-i\left(\mathrm{mod}k\right)$ to be that set $\left\{x-i\left(\mathrm{mod}k\right):x\in X\right\}$. Then we use $A_1,A_2,A_3,A_1-1,A_2-1,A_3-1$, $A_1-2,A_2-2,A_3-2,\cdots ,A_1-\left(n-1\right),A_2-\left(n-1\right),A_3-\left(n-1\right)$ to label $v_1,v_2,\cdots ,v_{3n}$. The last vertex $v_{3n+1}$ is labeled by $A_0$. We see that this is an $L^{\left(n\right)}\left(1,1\right)$ -labeling with span 3n of $C_m$.

Suppose $m>3n+1$. Then we label first $3n+1$ vertices as we did above. And then we repeatedly use $A_0,A_1$ and $A_2$ to label remaining vertices.

2) First consider $m=6n+2$. We use the sequence presented in (1) for $m=3n+1$ twice to label vertices of $C_{6n+2}$. Obviously, it is still an $L^{\left(n\right)}\left(1,1\right)$ -labeling for $C_{6n+2}$ with span 3n.

For $m>6n+2$, we label the first $6n+1$ vertices (namely, $v_1,v_2,\cdots ,v_{6n+1}$ ) using the same sequence as above and then repeat using $A_0,A_1$ and $A_2$ to label remaining vertices. Thus ${\lambda }_1^{\left(n\right)}\left(C_m\right)\le 3n$ in each case. On the other hand, by Lemma 3.2, we have the equality. ∎

Lemma 3.4. Let G be a diameter two graph with order p. Then ${\lambda }_1^{\left(n\right)}\left(G\right)=np-1$.

Proof. SinceG is a diameter two graph, every vertex must receive distinct label. Thus, we need at least np numbers, i.e., ${\lambda }_1^{\left(n\right)}\left(G\right)=np-1$. On the other hand, we can use $\left\{in,in+1,\cdots ,in+n-1\right\}$ for $i=0,1,\cdots ,p-1$ to label vertices of G in any order. Hence ${\lambda }_1^{\left(n\right)}\left(G\right)\le np-1$. ∎

Corollary 3.5.

${\lambda }_1^{\left(n\right)}\left(C_m\right)=\{\begin{array}{cc}5& m\equiv 0\left(\mathrm{mod}3\right),\\ 6& m\equiv 1\left(\mathrm{mod}3\right),m\ge 7\text{or}m\equiv 2\left(\mathrm{mod}3\right),m\ge 14,\\ 7& m=4,8,11,\\ 9& m=5.\end{array}$

Proof. Let $V\left(C_m\right)=\left\{v_1,v_2,\cdots ,v_m\right\}$ where $v_i$ is adjacent to $v_{i+1}$ for $i=1,2,\cdots ,m$ where $v_{m+1}=v_1$.

Claim 1. ${\lambda }_1^{\left(2\right)}\left(C_8\right)=7$.

Suppose ${\lambda }_1^{\left(2\right)}\left(C_8\right)\le 6$. Let f be an $L^{\left(2\right)}\left(1,1\right)$ -labeling with span 6. Since $m=8$, there must have three consecutive vertices, say $v_1,v_2$ and $v_3$, be labeled without using 6; and let $6\in f\left(v_4\right)$. Also let $f\left(v_1\right)=\left\{a_1,a_2\right\}$, $f\left(v_2\right)=\left\{b_1,b_2\right\}$ and $f\left(v_3\right)=\left\{c_1,c_2\right\}$. Then $f\left(v_4\right)=\left\{a,6\right\}$ where $a=a_1$ or $a_2$. Suppose $a=a_1$. Hence $f\left(v_5\right)\subseteq \left\{b_1,b_2,a_2\right\}$ and $f\left(v_8\right)\subset \left\{c_1,c_2,6\right\}$. Since $\left(f\left(v_6\right)\cup f\left(v_7\right)\right)\cap \left(f\left(v_5\right)\cup f\left(v_8\right)\right)=\varnothing$, we left only 3 numbers for $f\left(v_6\right)\cup f\left(v_7\right)$, (that is two from $\left\{b_1,b_2,a_2,c_1,c_2,6\right\}\backslash \left(f\left(v_5\right)\cup f\left(v_8\right)\right)$ plus $a_1$ ). It is not enough. The case for $a=a_2$ is similar.

Thus, ${\lambda }_1^{\left(2\right)}\left(C_8\right)\ge 7$. On the other hand, we can use $\left\{0,1\right\},\left\{2,3\right\},\left\{4,5\right\},\left\{6,7\right\}$ consecutively to label $v_1,v_2,\cdots ,v_8$ to obtain an $L^{\left(2\right)}\left(1,1\right)$ -labeling with sapn 7. Hence the claim holds.

Claim 2. ${\lambda }_1^{\left(2\right)}\left(C_{11}\right)=7$.

Let f be an $L^{\left(2\right)}\left(1,1\right)$ -labeling with span 6. Similar to Claim 1, we may assume that $f\left(v_1\right)=\left\{a_1,a_2\right\}$, $f\left(v_2\right)=\left\{b_1,b_2\right\}$, $f\left(v_3\right)=\left\{c_1,c_2\right\}$ and $f\left(v_4\right)=\left\{6,a\right\}$ where $a\in \left\{a_1,a_2\right\}$ and $6\notin \left\{a_1,a_2,b_1,b_2,c_1,c_2\right\}$.

Again, we have $f\left(v_{11}\right)\subset \left\{c_1,c_2,6\right\}$. Consider the following cases:

1) $f\left(v_8\right)\subset \left\{c_1,c_2,6\right\}$. Since $f\left(v_4\right)=\left\{6,a\right\}$ (as indicated above), the discussion on $f\left(v_4\right),f\left(v_5\right),f\left(v_6\right),f\left(v_7\right)$ and $f\left(v_8\right)$ is the same as Claim 1.

2) $f\left(v_8\right)\subset \left\{a_1,a_2,b_1,b_2,6\right\}$. Since $f\left(v_1\right)=\left\{a_1,a_2\right\}$, $f\left(v_{10}\right)\cap \left\{a_1,a_2\right\}=\varnothing$. Let $c\in \left\{c_1,c_2,6\right\}\backslash f\left(v_{11}\right)$. Hence $f\left(v_9\right)\subset \left\{a_1,a_2,c\right\}$. So $f\left(v_8\right)\subset \left\{b_1,b_2,c\right\}$. Thus, there is only one number left available for $f\left(v_{10}\right)$. This is a contradiction.

3) Suppose $f\left(v_8\right)$ consists of one number of $f\left(v_1\right)$ and one number of $f\left(v_3\right)$. Without loss of generality, say $f\left(v_8\right)=\left\{a_1,c_1\right\}$. Then $f\left(v_5\right)\subset \left\{b_1,b_2,a^{\prime }\right\}$ where $a^{\prime }=a_2$ if $a=a_1$ and vice versa. Then there only three numbers available for $f\left(v_6\right)\cup f\left(v_7\right)$ and they are one from $\left\{b_1,b_2,a^{\prime }\right\}\backslash f\left(v_5\right)$, $c_1$ and 6. That is not enough.

Therefore, ${\lambda }_1^{\left(2\right)}\left(C_{11}\right)\ge 7$. On the other hand, we can use $\left\{0,1\right\},\left\{2,3\right\},\left\{4,5\right\},\left\{6,7\right\}$ consecutively to label $v_1,v_2,\cdots ,v_{11}$ to obtain an $L^{\left(2\right)}\left(1,1\right)$ -labeling with span 7. Hence the claim holds. Finally, we have

1) $m\equiv 0\left(\mathrm{mod}3\right)$.

By Proposition 3.2, ${\lambda }_1^{\left(2\right)}\left(C_m\right)=5$.

2) $m\equiv 1\left(\mathrm{mod}3\right)$.

By Proposition 3.3, ${\lambda }_1^{\left(2\right)}\left(C_m\right)=6$ if $m\ge 7$. Since C₄ is diameter 2 graph, by Lemma 3.4, ${\lambda }_1^{\left(2\right)}\left(C_4\right)=7$.

3) $m\equiv 2\left(\mathrm{mod}3\right)$.

By Proposition 3.3, ${\lambda }_1^{\left(2\right)}\left(C_m\right)=6$ if $m\ge 14$. Case for $m=11$ and 8 are obtained by Claim 1 and Claim 2. Since C₅ is also a diameter 2 graph, by Lemma 3.4, ${\lambda }_1^{\left(2\right)}\left(C_5\right)=9$. ∎

4. Concluding Remark

We have obtained values of ${\lambda }_1^{\left(2\right)}\left(C_m\right)$ for all m and ${\lambda }_1^{\left(n\right)}\left(C_m\right)$ for some m where $n\ge 3$. Otherwise, the labeling numbers are still unknown. It is known that ${\lambda }_1\left(C_m\right)=4$ if $m\ne 0\left(\mathrm{mod}3\right)$ (cf. [8] ). Hence an upper bound is $4n-1$ in this case. On the other hand, the lower bound we have in Lemma 3.2 is 3n. Thus, there is still a gap between 3n and $4n-1$ for $n>1$.

Acknowledgements

The author would like to thank the referee for valuable editorial suggestions.

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1]	Yeh, R.K. (2019) Pair L(2,1)-Labelings of Infinite Graphs. Discussiones Mathematicae Graph Theory, 39, 257-269. https://doi.org/10.7151/dmgt.2077
[2]	Roberts, F.S. (1988) Private Communication with Griggs J. R.
[3]	Griggs, J.R. and Yeh, R.K. (1992) Labelling Graphs with a Condition at Distance 2. SIAM Journal on Discrete Mathematics, 5, 586-595. https://doi.org/10.1137/0405048
[4]	Calamoneri, T. (2011) The L(h,k)-Labeling Problems: A Update Survey and Annotated Bibliography. The Computer Journal, 54, 1344-1371. https://doi.org/10.1093/comjnl/bxr037
[5]	Yeh, R.K. (2006) A Survey on Labeling Graphs with a Condition at Distance Two. Discrete Mathematics, 306, 1217-1231. https://doi.org/10.1016/j.disc.2005.11.029
[6]	Füredi, Z., Griggs, J.R. and Kleitman, D.J. (1989) Pair Labellings with Given Distance. SIAM Journal on Discrete Mathematics, 2, 491-499. https://doi.org/10.1137/0402044
[7]	Griggs, J.R. and Jin, X.T. (2008) Real Number Channel Assignments for Lattices. SIAM Journal on Discrete Mathematics, 22, 996-1021. https://doi.org/10.1137/060650982
[8]	Liu, D.D.-F. and Yeh, R.K. (1997)On Distance Two Labelings of Graphs. Ars Combinatoria, 47, 13-22.