A Note on n-Set Distance-Labelings of Graphs
Show more
Abstract: This note is considered as a sequel of Yeh . 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.

1. Introduction

Inspired by a channel assignment problem proposed by Roberts  in 1988, Griggs and Yeh  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  or  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 $‖A-B‖=\mathrm{min}\left\{|a-b|: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 , 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 $|f\left(u\right)-f\left(v\right)|\ge {\delta }_{i}$ whenever the distance between u andv inG isi, for $i=1,2$. (The minimum value and the maximum value of ${\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  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.  ). 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.  ).

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 $‖{g}_{f}\left(u\right)-{g}_{f}\left(v\right)‖=\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  ). 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 Cm 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 Cm 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 Cm 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 Cm where $m\equiv 0\left(\mathrm{mod}3\right)$, to obtain an ${L}^{\left(n\right)}\left(1,1\right)$ -labeling of Cm 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 Cm be a cycle of order m where $m\overline{)\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, $|A\cup B\cup C|=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\overline{)\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)=\left\{\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{\hspace{0.17em}}\text{ }\text{or}\text{\hspace{0.17em}}\text{ }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\}\\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\}\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\}\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 C4 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 C5 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.  ). 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.

Cite this paper: Yeh, R. (2021) A Note on n-Set Distance-Labelings of Graphs. Open Journal of Discrete Mathematics, 11, 55-60. doi: 10.4236/ojdm.2021.113005.
References

   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

   Roberts, F.S. (1988) Private Communication with Griggs J. R.

   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

   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

   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

   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

   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

   Liu, D.D.-F. and Yeh, R.K. (1997)On Distance Two Labelings of Graphs. Ars Combinatoria, 47, 13-22.

Top