A Note on n-Set Distance-Labelings of Graphs

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.

Share and Cite:

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.

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 A B = min { | a b | : a A , b B } . Denote the set

[ k ] = { 0 , 1 , , k } and ( [ k ] n ) the collection of alln-subsets of [ k ] .

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

Let G = ( V , E ) be a graph and n be a positive integer. Given non-negative integers δ 1 δ 2 an L ( n ) ( δ 1 , δ 2 ) -labeling is a function f : V ( G ) ( [ k ] n ) for

some k 1 such that | f ( u ) f ( v ) | δ i whenever the distance between u andv inG isi, for i = 1 , 2 . (The minimum value and the maximum value of v V ( G ) f ( v ) is 0 and k, respectively.) The value kis called the span of f. The smallest k so that there is an L ( n ) ( δ 1 , δ 2 ) -labeling f with span k, is denoted by λ ( n ) ( G ; δ 1 , δ 2 ) and called the L ( n ) ( δ 1 , δ 2 ) -labeling number of G. An L ( n ) ( δ 1 , δ 2 ) -labeling with span λ ( n ) ( G ; δ 1 , δ 2 ) is called an optimal L ( n ) ( δ 1 , δ 2 ) -labeling. If n = 1 then notations L ( 1 ) and λ ( 1 ) will be simplified as L and λ , respectively.

Note: 1) The elements in [ k ] are called “numbers” and f ( u ) 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 ( δ 1 , 0 ) -labeling for δ 1 1 .

Previously, we have studied the L ( 2 ) ( 2 , 1 ) -labeling problem (cf. [1] ). In this note, we will first investigate properties of the L ( n ) ( δ 1 , δ 2 ) for n 1 . Then, we study the case of ( δ 1 , δ 2 ) = ( 1 , 1 ) .

2. Preliminarily

Let G be a graph and n an positive integer. Now, we construct a new graph G ( n ) by replacing each vertex v in G by n vertices v i , 1 i n and u i is adjacent to v j for all i , j , in G ( n ) , 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 ( 1 ) = G .

It is easy to verify that λ ( n ) ( G ; δ 1 , 1 ) = λ ( G ( n ) ; δ 1 , 1 ) . Thus, for example, λ ( n ) ( K m ; 2 , 1 ) = λ ( K n , n , , n ; 2 , 1 ) = n m + m 2 , where m 2 , by previous result on complete m-partite graph K n , n , , n (cf. [3] ).

Next, we consider the relation between the labeling numbers for n = 1 and n 1 . In the following, λ ( G ; 1 , 1 ) and λ ( n ) ( G ; 1 , 1 ) are denoted by λ 1 ( G ) and λ 1 ( n ) ( G ) , respectively, for short.

Proposition 2.1. Let n 1 , δ 1 δ 2 be nonnegative integers and Δ be the maximum degree of G. Then

1) ( n 1 ) ( Δ + 1 ) + δ 1 + ( Δ 1 ) δ 2 λ ( n ) ( G ; δ 1 , δ 1 ) .

2) λ ( n ) ( G ; δ 1 , δ 1 ) λ ( G ; n + δ 1 1 , n + δ 2 1 ) + 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 ( δ 1 , δ 2 ) condition), we shall have the trivial lower bound.

2) Let λ ( G ; n + δ 1 1 , n + δ 2 1 ) = k and f an optimal L ( n + δ 1 1 , n + δ 2 1 ) -labeling. Define sets L i = { i , i + 1 , , i + n 1 } , i = 0 , 1 , , k and function

g f : V ( G ) ( [ k + n 1 ] n ) by g f ( u ) = L i whenever f ( u ) = i for i = 0 , 1 , , k .

Let u and v be distinct vertices with d G ( u , v ) = j for j = 1 , 2 in G. Suppose f ( u ) = i and f ( v ) = i + n + δ j 1 for δ j δ j for j = 1 , 2 . Then g f ( u ) = { i , i + 1 , , i + n 1 } and g f ( v ) = { i + n + δ j 1 , i + n + δ j , , i + n + δ j 1 + n 1 } . Hence g f ( u ) g f ( v ) = ( i + n + δ j ) ( i + n 1 ) = δ j δ j for j = 1 , 2 . Thus g f is an L ( n ) ( δ 1 , δ 2 ) -labeling with span k + n 1 . Therefore

λ ( n ) ( G ; δ 1 , δ 1 ) λ ( G ; n + δ 1 1 , n + δ 2 1 ) + n 1 . ∎

The following is the direct consequence of Proposition 2.1 when ( δ 1 , δ 1 ) = ( 1 , 1 ) . Also notice that λ ( G ; d δ 1 , d δ 2 ) = d λ ( G ; δ 1 , δ 2 ) .

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

( Δ + 1 ) n 1 λ 1 ( n ) ( G ) n λ 1 ( G ) + n 1 . ∎

By Corollary 2.2, we know that whenever λ 1 ( G ) = Δ , the lower bound and the upper bound are equal and hence λ 1 ( n ) ( G ) = ( Δ + 1 ) n 1 . There are several well-known classes of graphs whose λ 1 values are all Δ (see [7] ). For example, tree T, wheel W m (with m rims), the square lattice Γ S (4-regular infinite plane graph), the hexagonal lattice Γ H (3-regular infinite plane graph), and the triangular lattice Γ Δ (6-regular infinite plane graph) are all with λ 1 = Δ . We summarize as follows.

Theorem 2.3.

1) λ 1 ( n ) ( T ) = ( Δ ( T ) + 1 ) n 1 .

2) λ 1 ( n ) ( W m ) = ( m + 1 ) n 1 .

3) λ 1 ( n ) ( Γ S ) = 5 n 1 .

4) λ 1 ( n ) ( Γ H ) = 4 n 1 .

5) λ 1 ( n ) ( Γ Δ ) = 7 n 1 . ∎

3. Cycles

We know that the maximum degree of a cycle Cm of order m 3 is 2. However, λ 1 ( C m ) is not necessary 2. It depends on m. In this section, we will consider L ( n ) ( 1 , 1 ) -labelings on cycles.

Proposition 3.1. Let Cm be a cycle of order m 3 . Then λ 1 ( n ) ( C m ) = 3 n 1 if m 0 ( mod 3 ) .

Proof. Since the maximum degree of Cm is 2, the trivial lower bound is 3 n 1 by Corollary 2.2. On the other hand, we use { 0 , 1 , , n 1 } , { n , n + 1 , , 2 n 1 } and { 2 n , 2 n + 1 , , 3 n 1 } consecutively to label vertices of Cm where m 0 ( mod 3 ) , to obtain an L ( n ) ( 1 , 1 ) -labeling of Cm with span 3 n 1 . Thus, we have the exact value of λ 1 ( n ) ( C m ) in this case. ∎

Lemma 3.2. Let Cm be a cycle of order m where m 0 ( mod 3 ) . Then λ 1 ( n ) ( C m ) 3 n .

Proof. Let V ( C m ) = { v 1 , v 2 , , v m } where v i is adjacent to v i + 1 for i = 1 , 2 , , m where v m + 1 = v 1 . Suppose λ 1 ( n ) ( C m ) 3 n 1 . Letf be an L ( n ) ( 1 , 1 ) -labeling with span 3 n 1 . Let f ( v 1 ) = A , f ( v 2 ) = B and f ( v 3 ) = C . Since, by definition, f ( v 1 ) , f ( v 2 ) and f ( v 3 ) are distinct, that is, | A B C | = 3 n and A B C = [ 3 n 1 ] . Now, f ( v 4 ) ( B C ) = and f ( v 4 ) [ 3 n 1 ] . Hence f ( v 4 ) = A . Consider f ( v 5 ) . Again, we have f ( v 5 ) ( A C ) = and f ( v 5 ) [ 3 n 1 ] . Hence f ( v 5 ) = B . In general, we have 1) f ( v i ) = A if i 1 ( mod 3 ) , 2) f ( v i ) = B if i 2 ( mod 3 ) and 3) f ( v i ) = C if i 0 ( mod 3 ) , for i = 1 , 2 , , m .

If m 1 ( mod 3 ) then f ( v m ) = A . But v m is adjacent to v 1 , where

f ( v 1 ) = A . This violates the condition on adjacent vertices. If m 2 ( mod 3 ) then f ( v m ) = B = f ( v 2 ) 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, λ 1 ( n ) ( C m ) 3 n for m 0 ( mod 3 ) . ∎

Proposition 3.3. If 1) m 1 ( mod 3 ) and m 3 n + 1 or 2) m 2 ( mod 3 ) and m 6 n + 2 then λ 1 ( n ) ( C m ) = 3 n .

Proof. Let V ( C m ) = { v 1 , v 2 , , v m } .

1) Suppose m = 3 n + 1 and Define A 0 = { 0 , 1 , , n 1 } , A 1 = { n , n + 1 , , 2 n 1 } , A 2 = { 2 n , 2 n + 1 , , 3 n 1 } and A 3 = { 3 n , 0 , , n 2 } . Denote X i ( mod k ) to be that set { x i ( mod k ) : x X } . 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 , , A 1 ( n 1 ) , A 2 ( n 1 ) , A 3 ( n 1 ) to label v 1 , v 2 , , v 3 n . The last vertex v 3 n + 1 is labeled by A 0 . We see that this is an L ( n ) ( 1 , 1 ) -labeling with span 3n of C m .

Suppose m > 3 n + 1 . Then we label first 3 n + 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 = 6 n + 2 . We use the sequence presented in (1) for m = 3 n + 1 twice to label vertices of C 6 n + 2 . Obviously, it is still an L ( n ) ( 1 , 1 ) -labeling for C 6 n + 2 with span 3n.

For m > 6 n + 2 , we label the first 6 n + 1 vertices (namely, v 1 , v 2 , , v 6 n + 1 ) using the same sequence as above and then repeat using A 0 , A 1 and A 2 to label remaining vertices. Thus λ 1 ( n ) ( C m ) 3 n 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 λ 1 ( n ) ( G ) = n p 1 .

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

Corollary 3.5.

λ 1 ( n ) ( C m ) = { 5 m 0 ( mod 3 ) , 6 m 1 ( mod 3 ) , m 7 or m 2 ( mod 3 ) , m 14 , 7 m = 4 , 8 , 11 , 9 m = 5.

Proof. Let V ( C m ) = { v 1 , v 2 , , v m } where v i is adjacent to v i + 1 for i = 1 , 2 , , m where v m + 1 = v 1 .

Claim 1. λ 1 ( 2 ) ( C 8 ) = 7 .

Suppose λ 1 ( 2 ) ( C 8 ) 6 . Let f be an L ( 2 ) ( 1 , 1 ) -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 f ( v 4 ) . Also let f ( v 1 ) = { a 1 , a 2 } , f ( v 2 ) = { b 1 , b 2 } and f ( v 3 ) = { c 1 , c 2 } . Then f ( v 4 ) = { a , 6 } where a = a 1 or a 2 . Suppose a = a 1 . Hence f ( v 5 ) { b 1 , b 2 , a 2 } and f ( v 8 ) { c 1 , c 2 , 6 } . Since ( f ( v 6 ) f ( v 7 ) ) ( f ( v 5 ) f ( v 8 ) ) = , we left only 3 numbers for f ( v 6 ) f ( v 7 ) , (that is two from { b 1 , b 2 , a 2 , c 1 , c 2 , 6 } \ ( f ( v 5 ) f ( v 8 ) ) plus a 1 ). It is not enough. The case for a = a 2 is similar.

Thus, λ 1 ( 2 ) ( C 8 ) 7 . On the other hand, we can use { 0 , 1 } , { 2 , 3 } , { 4 , 5 } , { 6 , 7 } consecutively to label v 1 , v 2 , , v 8 to obtain an L ( 2 ) ( 1 , 1 ) -labeling with sapn 7. Hence the claim holds.

Claim 2. λ 1 ( 2 ) ( C 11 ) = 7 .

Let f be an L ( 2 ) ( 1 , 1 ) -labeling with span 6. Similar to Claim 1, we may assume that f ( v 1 ) = { a 1 , a 2 } , f ( v 2 ) = { b 1 , b 2 } , f ( v 3 ) = { c 1 , c 2 } and f ( v 4 ) = { 6 , a } where a { a 1 , a 2 } and 6 { a 1 , a 2 , b 1 , b 2 , c 1 , c 2 } .

Again, we have f ( v 11 ) { c 1 , c 2 , 6 } . Consider the following cases:

1) f ( v 8 ) { c 1 , c 2 , 6 } . Since f ( v 4 ) = { 6 , a } (as indicated above), the discussion on f ( v 4 ) , f ( v 5 ) , f ( v 6 ) , f ( v 7 ) and f ( v 8 ) is the same as Claim 1.

2) f ( v 8 ) { a 1 , a 2 , b 1 , b 2 , 6 } . Since f ( v 1 ) = { a 1 , a 2 } , f ( v 10 ) { a 1 , a 2 } = . Let c { c 1 , c 2 , 6 } \ f ( v 11 ) . Hence f ( v 9 ) { a 1 , a 2 , c } . So f ( v 8 ) { b 1 , b 2 , c } . Thus, there is only one number left available for f ( v 10 ) . This is a contradiction.

3) Suppose f ( v 8 ) consists of one number of f ( v 1 ) and one number of f ( v 3 ) . Without loss of generality, say f ( v 8 ) = { a 1 , c 1 } . Then f ( v 5 ) { b 1 , b 2 , a } where a = a 2 if a = a 1 and vice versa. Then there only three numbers available for f ( v 6 ) f ( v 7 ) and they are one from { b 1 , b 2 , a } \ f ( v 5 ) , c 1 and 6. That is not enough.

Therefore, λ 1 ( 2 ) ( C 11 ) 7 . On the other hand, we can use { 0 , 1 } , { 2 , 3 } , { 4 , 5 } , { 6 , 7 } consecutively to label v 1 , v 2 , , v 11 to obtain an L ( 2 ) ( 1 , 1 ) -labeling with span 7. Hence the claim holds. Finally, we have

1) m 0 ( mod 3 ) .

By Proposition 3.2, λ 1 ( 2 ) ( C m ) = 5 .

2) m 1 ( mod 3 ) .

By Proposition 3.3, λ 1 ( 2 ) ( C m ) = 6 if m 7 . Since C4 is diameter 2 graph, by Lemma 3.4, λ 1 ( 2 ) ( C 4 ) = 7 .

3) m 2 ( mod 3 ) .

By Proposition 3.3, λ 1 ( 2 ) ( C m ) = 6 if m 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, λ 1 ( 2 ) ( C 5 ) = 9 . ∎

4. Concluding Remark

We have obtained values of λ 1 ( 2 ) ( C m ) for all m and λ 1 ( n ) ( C m ) for some m where n 3 . Otherwise, the labeling numbers are still unknown. It is known that λ 1 ( C m ) = 4 if m 0 ( mod 3 ) (cf. [8] ). Hence an upper bound is 4 n 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 4 n 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.

Copyright © 2021 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.