L(2,1)-Labeling of the Brick Product Graphs

Xiujun Zhang^1,2, Hong Yang², Hong Li²

¹School of Information Science and Engineering, Chengdu University, Chengdu, China.
²Key Laboratory of Pattern Recognition and Intelligent Information Processing, Institutions of Higher Education of Sichuan Province, Chengdu University, Chengdu, China.

DOI: 10.4236/jamp.2017.58126                

Abstract

A k-L(2,1)-labeling for a graph G is a function such that whenever and whenever u and v are at distance two apart. The λ-number for G, denoted by λ(G), is the minimum k over all k-L(2,1)-labelings of G. In this paper, we show that for or 11, which confirms Conjecture 6.1 stated in [X. Li, V. Mak-Hau, S. Zhou, The L(2,1)-labelling problem for cubic Cayley graphs on dihedral groups, J. Comb. Optim. (2013) 25: 716-736] in the case when or 11. Moreover, we show that  if 1) either (mod 6), m is odd, r = 3, or 2) (mod 3), m is even (mod 2), r = 0.

Keywords

Graph Labeling, Brick Product Graph, L((2, 1)-Labeling, Frequency Assignment Problem

1. Introduction

Let be a graph. For two vertices u and v in G, the distance between u and v is the number of the edges of the shortest path between u and v. A k-L(2,1)-labeling for a graph G is a function such that whenever and whenever u and v are at distance two apart. The λ-number for G, denoted by, is the minimum k over all k-L(2,1)-labelings of G. This labeling problem of graphs was proposed by Griggs and Roberts [1] which is a variation of the frequency assignment problem introduced by Hale [2] . The frequency assignment problem asks for assigning frequencies to transmitters in a broadcasting network with the aim of avoiding undesired interference. One of the graph theoretical models of the frequency assignment problem is the notion of distance constrained labeling of graphs [3] [4] [5] .

The L(2,1)-labeling problem was studied very extensively in the literature and has attracted much attention. Griggs and Yeh [6] proposed a conjecture, which is called the -conjecture, that for any graph with, where is the maximum degree of G, and they also proved that. Later, it was shown that by Chang and Kuo [7] , by Král’ and Škrekovski [8] , and then by Goncalves [9] . Until now, this conjecture is still open. Nevertheless, it is still interesting to study the -conjecture, which has been confirmed for several classes of graphs, such as chordal graphs, outerplanar graphs, generalized Petersen graphs, Hamiltonian graphs with, two families of Hamming graphs etc (see [10] ). Havet et al. obtained a result implying that the -con- jecture is true for graphs with sufficiently large. Thus, we may need to study the L(2,1)-labelling problem for graphs with small. Motivated with this, the L(2,1)-labelling problem for the brick product graphs was studied [10] .

Let, and be integers such that is even. Let be a cycle of length. The -brick-product of, denoted by, is the graph with adjacency defined in two cases. For must be odd and is obtained from the cycle by adding chords joining and for, where subscripts are taken modulo. In the general case where, is obtained by first taking the vertex-disjoint union of m copies of, denoted by

(1)

Next, for each pair such that i and j have the same parity, an edge is added to join and. Finally, for odd, an edge is added to join and, where the second subscript is modulo.

Li et al. [10] proposed the following conjecture:

Conjecture 1. [10] or 6 for all brick products with and

Shao et al. [11] confirmed the above conjecture, i.e. it was proved that

Theorem 1. [11] if 1) is even, or 2) is odd and.

Therefore, Conjecture 1 is still open for odd and.

In this paper, we show that for or 11, which con- firms Conjecture 6.1 stated in [X. Li, V. Mak-Hau, S. Zhou, The L(2,1)-labelling problem for cubic Cayley graphs on dihedral groups, J. Comb. Optim. (2013) 25: 716-736] in the case when or 11. Moreover, we show that if 1) either (mod 6), m is odd, , 2) or (mod 3), m is even (mod 2),.

2. Main Results

From the definition of the brick product graph, it is clear that

Fact 1. is isomorphic to.

2.1. Some Results on the Upper Bound 6 of l-Number

In [6] , it was shown that

Lemma 1. [6] The λ-number of any connected cubic graph is at least 5.

Proposition 1. Let. Then for all.

By Theorem 1, we have for all and. Toge- ther with Fact 1, we only need to consider. Let

We use the pattern to label for, and in- duces a 6-L(2,1)-labeling of. Therefore, the case is settled.

Now, we consider the case. If for, we obtain a 6- L(2,1)-labeling of by repeating the leftmost four columns of; If for, we obtain a 6-L(2,1)-labeling of by re- peating the leftmost four columns of (see Figure 1). Therefore, for and.

Proposition 2. Let. Then for all.

Similar to Proposition 1, we only need to consider the case and 11.

Case 1:.

We use the following pattern to label for, and induces a 6-L(2,1)-labeling of. Therefore, the case is settled. Now, we consider the case. If for, we obtain a 6-L(2,1)-labeling of by repeating the leftmost four columns of; If for, we obtain a 6-L(2,1)-labeling of by re- peating the leftmost four columns of. Therefore, for and.

Figure 1. The 6-L(2,1)-labeling of induced by.

Case 2:.

We use the following pattern to label for, and induces a 6-L(2,1)-labeling of. Therefore, the case is settled. Now, we consider the case. If for, we obtain a 6-L(2,1)-labeling of by repeating the leftmost four columns of; If for, we obtain a 6-L(2,1)-labeling of by repeating the leftmost four columns of. Therefore, for and.

From Propositions 1 and 2, we have

Theorem 2. Let. Then we have for or 11.

2.2. Brick Product Graphs with l-Number 5

In [10] , it was proved that

Theorem 3. Let and be integers such that. Then

.

Moreover, if and only if one of the following holds:

1) 3 divides and 6 divides m;

2) 6 divides and 3 divides m.

Furthermore, if neither 1) nor 2) is satisfied, then pro- vided that (and is even or odd), or both and m are even.

However, Theorem 3 consider the condition that. There may exist other brick product graphs with λ-number 5 with the condition. We provide some brick product graphs with l-number 5 in the following:

Theorem 4. Let, with,. Then.

Let, , and, where is used for times. Then Q induces a 5-L(2,1)-labeling of, and so

.

Proposition 3. Let, ,. Then.

Let, and, where P is used for times. Then Q

induces a 5-L(2,1)-labeling of, and so.

Proposition 4. Let, ,. Then.

Let, and, where P is used for times.

Then Q induces a 5-L(2,1)-labeling of, and so.

Proposition 5. Let, ,. Then.

Let, and, where P is used for

times. Then Q induces a 5-L(2,1)-labeling of, and so .

Proposition 6. Let, m = 9, r = 3. Then.

Let, and, where P is used for

times. Then Q induces a 5-L(2,1)-labeling of, and so

.

By observing the results of Propositions 3 - 6, we propose the following con- jecture:

Conjecture 2. Let, ,. Then .

Acknowledgements

This work was supported by Applied Basic Research (Key Project) of Sichuan Province under grant 2017JY0095, Key Project of Sichuan Provincial Department of Education under grant 17ZA0079 and Automotive Creative Design Pilot Area of Chengdu University and Longquanyi District under grant 2015-CX00- 00010-ZF.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Roberts, F.S. (1988) Private Communication to J. R. Griggs.
[2]	Hale, W.K. (1980) Frequency Assignment: Theory and Applications. Annals of Operations Research, 76, 73-93. https://doi.org/10.1109/PROC.1980.11899
[3]	Whittlesey, M.A., Georges, J.P. and Mauro, D.W. (1995) On the λ number of Qn and related graphs. SIAM Journal on Discrete Mathematics, 8, 499-506. https://doi.org/10.1137/S0895480192242821
[4]	Shao, Z. and Vesel, A. (2014) L(2,1)-Labeling of the Strong Product of Paths and Cycles. The Scientific World Journal, 2014, 12.
[5]	Georges, J.P., Mauro, D.W. and Whittlesey, M.A. (1994) Relating Path Coverings to Vertex Labellings with a Condition at Distance Two. Discrete Mathematics, 135, 103-111.
[6]	Griggs, J.R. and Yeh, R.K. (1992) Labelling Graphs with a Condition at Distance Two. SIAM Journal on Discrete Mathematics, 5, 586-595. https://doi.org/10.1137/0405048
[7]	Chang, G.J. and Kuo, D. (1996) The L(2,1)-Labeling Problem on Graphs. SIAM Journal on Discrete Mathematics, 9, 309-316. https://doi.org/10.1137/S0895480193245339
[8]	Král', D. and Skrekovski, R. (2003) A Theorem about Channel Assignment Problem. SIAM Journal on Discrete Mathematics, 16, 426-437. https://doi.org/10.1137/S0895480101399449
[9]	Goncalves, D. (2008) On the L(p,1)-Labelling of Graphs. Discrete Mathematics, 308, 1405-1414. https://doi.org/10.1016/j.disc.2007.07.075
[10]	Li, X., Mak-Hau, V. and Zhou, S. (2013) The L(2,1)-Labelling Problem for Cubic Cayley Graphs on Dihedral Groups. Journal of Combinatorial Optimization, 25, 716-736. https://doi.org/10.1007/s10878-012-9525-4
[11]	Shao, Z., Xu, J. and Yeh, R.K. (2016) L(2,1)-Labeling for Brick Product Graphs. Journal of Combinatorial Optimization, 31, 447-462. https://doi.org/10.1007/s10878-014-9763-8