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 . Denote the set
and the collection of alln-subsets of .
Motivated by the article , we propose the following labeling on a graph.
Let be a graph and n be a positive integer. Given non-negative integers an -labeling is a function for
some such that whenever the distance between u andv inG isi, for . (The minimum value and the maximum value of is 0 and k, respectively.) The value kis called the span of f. The smallest k so that there is an -labeling f with span k, is denoted by and called the -labeling number of G. An -labeling with span is called an optimal -labeling. If then notations and will be simplified as L and , respectively.
Note: 1) The elements in are called “numbers” and is called the “label” of u. So, a label is a set in this problem. 2) Using our notation, the labeling in  is the -labeling for .
Previously, we have studied the -labeling problem (cf.  ). In this note, we will first investigate properties of the for . Then, we study the case of .
Let G be a graph and n an positive integer. Now, we construct a new graph by replacing each vertex v in G by n vertices , and is adjacent to for all , in , whenever u and v is adjacent in G. That is, and , for all , induces a complete bipartite graph . Note that .
It is easy to verify that . Thus, for example, , where , by previous result on complete m-partite graph (cf.  ).
Next, we consider the relation between the labeling numbers for and . In the following, and are denoted by and , respectively, for short.
Proposition 2.1. Let , be nonnegative integers and Δ be the maximum degree of G. Then
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 condition), we shall have the trivial lower bound.
2) Let and f an optimal -labeling. Define sets , and function
by whenever for .
Let u and v be distinct vertices with for in G. Suppose and for for . Then and . Hence for . Thus is an -labeling with span . Therefore
The following is the direct consequence of Proposition 2.1 when . Also notice that .
Corollary 2.2. Let Δ be the maximum degree of G. Then
By Corollary 2.2, we know that whenever , the lower bound and the upper bound are equal and hence . There are several well-known classes of graphs whose values are all Δ (see  ). For example, tree T, wheel (with m rims), the square lattice (4-regular infinite plane graph), the hexagonal lattice (3-regular infinite plane graph), and the triangular lattice (6-regular infinite plane graph) are all with . We summarize as follows.
5) . ∎
We know that the maximum degree of a cycle Cm of order is 2. However, is not necessary 2. It depends on m. In this section, we will consider -labelings on cycles.
Proposition 3.1. Let Cm be a cycle of order . Then if .
Proof. Since the maximum degree of Cm is 2, the trivial lower bound is by Corollary 2.2. On the other hand, we use , and consecutively to label vertices of Cm where , to obtain an -labeling of Cm with span . Thus, we have the exact value of in this case. ∎
Lemma 3.2. Let Cm be a cycle of order m where . Then .
Proof. Let where is adjacent to for where . Suppose . Letf be an -labeling with span . Let and . Since, by definition, and are distinct, that is, and . Now, and . Hence . Consider . Again, we have and . Hence . In general, we have 1) if , 2) if and 3) if , for .
If then . But is adjacent to , where
. This violates the condition on adjacent vertices. If then while the distance between and is 2. Again, this violates the condition on distance 2 vertices. We have a contradiction on each case. Therefore, for . ∎
Proposition 3.3. If 1) and or 2) and then .
Proof. Let .
1) Suppose and Define , , and . Denote to be that set . Then we use , to label . The last vertex is labeled by . We see that this is an -labeling with span 3n of .
Suppose . Then we label first vertices as we did above. And then we repeatedly use and to label remaining vertices.
2) First consider . We use the sequence presented in (1) for twice to label vertices of . Obviously, it is still an -labeling for with span 3n.
For , we label the first vertices (namely, ) using the same sequence as above and then repeat using and to label remaining vertices. Thus 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 .
Proof. SinceG is a diameter two graph, every vertex must receive distinct label. Thus, we need at least np numbers, i.e., . On the other hand, we can use for to label vertices of G in any order. Hence . ∎
Proof. Let where is adjacent to for where .
Claim 1. .
Suppose . Let f be an -labeling with span 6. Since , there must have three consecutive vertices, say and , be labeled without using 6; and let . Also let , and . Then where or . Suppose . Hence and . Since , we left only 3 numbers for , (that is two from plus ). It is not enough. The case for is similar.
Thus, . On the other hand, we can use consecutively to label to obtain an -labeling with sapn 7. Hence the claim holds.
Claim 2. .
Let f be an -labeling with span 6. Similar to Claim 1, we may assume that , , and where and .
Again, we have . Consider the following cases:
1) . Since (as indicated above), the discussion on and is the same as Claim 1.
2) . Since , . Let . Hence . So . Thus, there is only one number left available for . This is a contradiction.
3) Suppose consists of one number of and one number of . Without loss of generality, say . Then where if and vice versa. Then there only three numbers available for and they are one from , and 6. That is not enough.
Therefore, . On the other hand, we can use consecutively to label to obtain an -labeling with span 7. Hence the claim holds. Finally, we have
By Proposition 3.2, .
By Proposition 3.3, if . Since C4 is diameter 2 graph, by Lemma 3.4, .
By Proposition 3.3, if . Case for and 8 are obtained by Claim 1 and Claim 2. Since C5 is also a diameter 2 graph, by Lemma 3.4, . ∎
4. Concluding Remark
We have obtained values of for all m and for some m where . Otherwise, the labeling numbers are still unknown. It is known that if (cf.  ). Hence an upper bound is 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 for .
The author would like to thank the referee for valuable editorial suggestions.