# Lp,q-Label Coloring Problem with Application to Channel Allocation

Authors: Zhenbin Liu; Yuqiang Wu
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

In this paper, theLp,q-coloring problem of the graph is studied with application to channel allocation of the wireless network. First, by introducing two new logical operators, some necessary and sufficient conditions for solving the Lp,q-coloring problem are given. Moreover, it is noted that all solutions of the obtained logical equations are corresponding to each coloring scheme. Second, by using the semitensor product, the necessary and sufficient conditions are converted to an algebraic form. Based on this, all coloring schemes can be obtained through searching all column indices of the zero columns. Finally, the obtained result is applied to analyze channel allocation of the wireless network. Furthermore, an illustration example is given to show the effectiveness of the obtained results in this paper.


---

## Body

## 1. Introduction

It is well known that the coloring problem is a basic and classical problem in graph theory. Graph coloring is originated from famous conjecture called four-colour conjecture [1] and widely used in many real-life areas [2–4], such as scheduling and timetabling in engineering, air traffic flow management, and channel allocation of mobiles. There are various forms of graph coloring, such as set coloring, list coloring, T-coloring, and Ln1,n2,⋯,ns-coloring (ni denotes a nonnegative integer, i=1,2,⋯,s). The labeling problems of graphs arise in many networking and telecommunication contexts. The channel allocation problem is first formulated as a graph coloring problem by Hale [5]. Furthermore, Griggs and Yeh formulated this problem as a graph labeling problem [6]. Lp,q-label coloring is one kind of graph labeling, which has major application in channel allocation [5, 7–10]. Thus, it is still more interesting to introduce a new method to study the coloring problem.Recently, Cheng et al. and Li et al. provided a new mathematical method, which is called the semitensor product with matrices [11–13] to study logical systems [14–23], probability logical networks [24, 25], game theory [26, 27], coloring problem [1, 10, 28], and some other related fields [29–31]. Wang et al. first studied the graph problem by using the semitensor product [1]. In [1], the maximum (weight) stable set and vertex coloring problems of graphs were investigated with application to the group consensus of multiagent systems, and an algorithm was established to find all the internally stable sets for any graph. In [28], Zhong et al. investigated the minimum stable set and core of the graph and established an algorithm to find all the externally stable sets.This paper studies theLp,q-coloring problem of the graph with application to channel allocation of the wireless network. Some necessary and sufficient conditions for solving the Lp,q-coloring problem are first made by introducing two new logical operators. Moreover, it is noted that all solutions of the obtained logical equations are corresponding to each coloring scheme. Then, by using the semitensor product, the necessary and sufficient conditions are converted to an algebraic form. Based on this, all coloring schemes can be obtained through searching all column indices of the zero columns. Finally, the obtained results are applied to analyze channel allocation of the wireless network. Furthermore, an illustration example is given to show the effectiveness of the obtained results in this paper.The rest of this paper is organized as follows. Section2 gives some necessary preliminaries on the semitensor product of matrices and Lp,q-labeling. The main results are shown in Section 3. In Section 4, we apply the obtained results to the channel allocation of the wireless network, which is followed by the conclusion in Section 5.


## 2. Preliminaries

In this section, we give some necessary preliminaries on the semitensor product, the pseudo-Boolean function, and graph theory, which will be used in the sequel.First, we give some notations to be used in this paper.Dk=0,1,⋯,k−1, especially, D:=D2=0,1.δni: the i-th column of the identity matrix In.Denote byColbB the b-th column of matrix B and by ColB the set of all columns of matrix B.ℝn×r: the set of n×r real matrices, where ℝ denotes the set of real numbers.Δn:=δnii=1,2,⋯,n, and for simplicity, let Δ:=Δ2. Identify k−i∼δki, i=1,2,⋯,k, which implies Dk∼Δk, where p∼q means they are equivalent.A matrixL∈ℝn×r is called a logical matrix if columns of L are of the form of δni. Denote by ℒn×r the set of n×r logical matrices.IfL∈ℒn×r, it can be expressed as L=δni1δni2⋯δnir. For the sake of compactness, it is briefly denoted by L=δni1i2⋯ir.Next, we give some definitions and results about the semitensor product.Definition 1.
(see [11]). The semitensor product of two matrices A∈ℝm×n and B∈ℝp×q is(1)A∝B=A⊗Iα/nB⊗Iα/p,where α=lcmn,p is the least common multiple of n and p and ⊗ is the Kronecker product.
Throughout this paper, the default matrix product is the semitensor product. The semitensor product is a generalization of the conventional matrix product. Thus, we can simply call it “product” and omit the symbol “<imes” without confusion.Definition 2.
(see [11]). A swap matrix Wm,n is an mn×mn matrix defined as follows: its rows and columns are labeled by double index i,j, the columns are arranged by the ordered multiindex Idi,j;m,n, and the rows are arranged by the ordered multiindex Idj,i;n,m. Then, the element at the position I,J,i,j is(2)wI,Ji,j=δi,jI,J=1,I=iandJ=j;0,otherwise.Remark 1.
Whenm=n, Wm,n is briefly rewritten as Wn. Furthermore, from Definition 2, Wm,n can be written as the following form for all m, n:(3)Wm,n=δmn1m+1⋯i−1m+1⋯n−1m+12m+2⋯i−1m+2⋯n−1m+2⋮mm+m⋯i−1m+m⋯n−1m+m,orWm,n=δn1∝δm1⋯δnn∝δm1⋮δn1∝δm2⋯δnn∝δm2⋮⋯⋮δn1∝δmm⋯δnn∝δmm.
Now, we list some basic properties of the semitensor product [11]:(1)
LetX∈ℝm and Y∈ℝn be column vectors. Then,(4)Wm,nXY=YX.(2)
LetX∈ℝt be a column vector. Then,(5)XA=It⊗AX.(3)
LetX=δti∈ℝt be a logical vector. Then,(6)X2=Mr,tX,where(7)Mr,t=δt21t+2⋯i−1t+i⋯t2=δt1∝δt1δt2∝δt2⋯δtt∝δtt∈ℒt2×t.(4)
LetX=δti∈ℝt be a logical vector and A∈ℝm×nt. Then,(8)AX=Ai,where Ai∈ℝm×n is the i-th block of A=A1A2⋯At. Especially, when n=1,(9)AX=ColiA.Lemma 1 .(see [11]).
Any logical functiony=fx1,x2,⋯,xn with logical variables xi∈Dk, i=1,⋯,n, can be expressed in a multilinear form as(10)y=fx1,x2,⋯,xn=Mfx1x2⋯xn,where y∈Δk and Mf∈ℒk×kn is unique, called the structural matrix of f.Remark 2.
The first row of the structural matrixMf corresponds to the truth value of the logical function fx1,x2,⋯,xs.
Now, we list the structural matrices for some basick-valued logical operators [11], which will be used later.
Negation (¬): ¬x=k−1−x, which has a structural matrix as Mn,k=δkkk−1⋯21.
Conjunction (∧): x∧y=minx,y, which has a structural matrix as(11)Mc,k=δk123⋯k⋮223⋯k⋮333⋯k⋮⋯⋮kkk⋯k.
Disjunction (∨): x∨y=maxx,y, which has a structural matrix as(12)Md,k=δk111⋯1⋮122⋯2⋮123⋯3⋮⋯⋮123⋯k.
Exclusive or (∨¯): x∨¯y=1,x=y0,x≠y, which has a structural matrix as(13)M∨¯,k=δk1kk⋯k⋮k1k⋯k⋮kk1⋯k⋮⋯⋮kkk⋯1.
Dummy operator (σd): σdx2=x, which has a structural matrix as(14)Ed,k=δk123⋯k⋮⋯⋮123⋯k.
The following concepts and properties will be used in the next section.Definition 3.
(see [12]). An n-ary pseudo-Boolean function fx1,x2,⋯,xn is a mapping from Dn to ℝ, where Dn:=D×D×⋯×D︸n.
A graphG consists of a vertex (node) set V=v1,v2,⋯,vn and an edge set E⊂V×V denoted by G=V,E.Lemma 2 .(see [32]).
Given a simple graphG=V,E, an Lp,q-labeling f of G is an integer assignment f:V⟶1,2,⋯,k such that(15)fu−fv≥p,du,v=1,q,du,v=2,where u,v∈V, du,v denotes the distance between u and v, and p,q are two given positive integers.


## 3. Main Results

In this section, we investigate theLp,q-label coloring problem by the semitensor product method and present the main results of this paper.Consider a graphG with n nodes V=v1,v2,⋯,vn. Assume that the adjacency matrix, A=aij, of G is given as(16)aij=1,vj∈Ni0,vj∉Ni,where Ni denotes a neighbor set of node i.It is noted thataij=aji for an undirected graph and aii=0 in our study since the graph G is a simple graph. Furthermore, let B=bij, where bii=0 and bij=ai1×bb1j+bai2×bb2j+b⋯+bain×bbnj, ×b”“ and +b”“ are, respectively, Boolean addition and Boolean multiplication. It is easy to obtain that dvi,vj=1 when aij=1 and dvi,vj=2 when bij=1.LetS=0,1,2,⋯,k−1. For all vi∈V, assign it an integer yi∈S, i.e., fvi=yi. We need two logical operators as(17)⊘k+x=x+1,x=0,1,2,⋯,k−2;k−1,x=k−1;⊘k−x=x−1,x=1,2,⋯,k−2,k−1;0,x=0.Moreover, the structural matrices are(18)M⊘k+=δk112⋯k−1,M⊘k−=δk23⋯kk.Then, we have the following result to determine whether theLp,q-label problem is solved.Theorem 1.
Consider an undirected graphG with n nodes V=v1,v2,⋯,vn. Its Lp,q-label problem is solved if and only if the logical equations(19)∑i=1n∑j>iaij∨s=0p−1yi∨¯⊘k+syj∨yi∨¯⊘k−syj=0.∑i=1n∑j>ibij∨s=0q−1yi∨¯⊘k+syj∨yi∨¯⊘k−syj=0,are solved. That is,(20)∑i=1n∑j>iaij∨s=0p−1yi∨¯⊘k+syj∨yi∨¯⊘k−syj+bij∨s=0q−1yi∨¯⊘k+syj∨yi∨¯⊘k−syj=0,is solved.Proof.
Necessity: assume thatLp,q coloring of G is solvable, and A=aij is the adjacent matrix of the graph G. For all vi and vj∈Vvi≠vj, when dvi,vj=1, fvi−fvj|≥p. It is easy to see that dvi,vj=1⇔aij=1 and fvi−fvj|≥p⇔fvi≠fvj±s, s=0,1,2,⋯,p−1. That is, yi≥yj+p when yi≥yj or yi≤yj−p when yi≤yj.
Sinceyi∈0,1,⋯,k−1, we introduce the logical operators ⊘k+ and ⊘k−, and then we have yi≥yj+p is equivalent to ∨s=0p−1yi∨¯⊘k+syj=0, and yi≤yj−p is equivalent to ∨s=0p−1yi∨¯⊘k−syj=0. That is, fvi−fvj|≥p is equivalent to(21)∨s=0p−1yi∨¯⊘k+syj∨yi∨¯⊘k−syj=0.
Then, we haveaij∨s=0p−1yi∨¯⊘ksyj∨yi∨¯⊘ksyj=0 for all i,j. Since aij=aji for the undirected graph and yi−yj|=|yj−yi, we obtain that(22)∑i=1n∑j>iaij∨s=0p−1yi∨¯⊘k+syj∨yi∨¯⊘k−syj=0.
SetB=bij, where bij=ai1×ba1j+bai2×ba2j+b⋯+bain×banji≠j and bii=0, i,j=1,2,⋯,n. Obviously, dvi,vj=2⇔bij=1. Similarly, when dvi,vj=2, we have(23)∑i=1n∑j>ibij∨s=0q−1yi∨¯⊘k+syj∨yi∨¯⊘k−syj=0.
Therefore, from (22) and (23), we obtain that (19) is satisfied, and the necessity is proved.
Sufficiency: suppose that (19) is satisfied. Then, for all i,j, we have(24)aij⋅∨s=0p−1yi∨¯⊘k+syj∨yi∨¯⊘k−syj=0,bij⋅∨s=0q−1yi∨¯⊘k+syj∨yi∨¯⊘k−syj=0.
From (24), if aij=1, ∨s=0p−1yi∨¯⊘k+syj∨yi∨¯⊘k−syj=0. Then, yi∨¯⊘k+syj=0 or yi∨¯⊘k−syj=0, i.e., yi≠yj±s, s=0,1,⋯,p−1. Therefore, yi−yj|≥p. Similarly, if bij=1, yi−yj|≥q by (24).
Sinceaij=1⇔dvi,vj=1 and bij=1⇔dvi,vj=2, we have the Lp,q coloring of the graph G is solvable, and the proof is complete.
It is note that, for a directed graphG, we have the following corollary.Corollary 1.
Consider a directed graphG with n nodes V=v1,v2,⋯,vn. Its Lp,q-label problem is solved if and only if(25)∑i=1n∑j≠iaij∨s=0p−1yi∨¯⊘k+syj∨yi∨¯⊘k−syj+bij∨s=0q−1yi∨¯⊘k+syj∨yi∨¯⊘k−syj=0,is solved.Letx=δkk−y, y∈S=0,1,2,⋯,k−1. Then, y=k−1,k−2,⋯,1,0x. Using the semitensor product and the vector form of logical variables, we have the following results.Theorem 2.
Logical equations (19) are solved if and only if there exists at least an integer v1≤v≤kn such that the v-th column of matrix M is 0, where(26)M=∑i=1n∑j>iaijMij,p+bijMij,q,Mij,s=MsMij,i,j=1,2,⋯,n,i≠j,s=p,q,Ms=JkMd,ks−1Q0Ik2⊗Q1Mr,k2⋯Ik2⊗QsMr,k2,Mij=Ed,kn−2Wkj,kn−jWki,kj−1−ii<j,Ql=Md,kM∨¯,kIk⊗M⊘k+lIk2⊗M∨¯,kIk⊗M⊘k−lMr,k2,l=0,1,⋯,s−1,Jk=k−1k−2⋯10, and the product is ∝”“Proof.
Using the semitensor product and the vector form of logical variables, there exists one matrixM∈R1×kn such that the left-hand side of equation (13) is Mx1x2⋯xn, where xi=δkk−yi∈Δk, i=1,2,⋯,n. Equation (13) is solved if and only if there exists at least an integer i1≤i≤kn such that the ith column of matrix M is 0. Now, we only need to study matrix M.
Since the logical form ofyi∨¯⊘k+syj∨yi∨¯⊘k−syj is(27)Md,kM∨¯,kxiM⊘k+sxjM∨¯,kxiM⊘k−sxj=Md,kM∨¯,kIk⊗M⊘k+sxixjM∨¯,kIk⊗M⊘k−sxixj=Md,kM∨¯,kIk⊗M⊘k+sIk2⊗M∨¯,kIk⊗M⊘k−sxixj2=Md,kM∨¯,kIk⊗M⊘k+sIk2⊗M∨¯,kIk⊗M⊘k−sMr,kxixj≜Qsxixj,we have(28)∨s=0p−1yi∨¯⊘k+syj∨yi∨¯⊘k−syj=JkMd,kp−1Q0xixjQ1xixj⋯Qp−1xixj=JkMd,kp−1Q0Ik2⊗Q1Mr,k2xixj=JkMd,kp−1Q0Ik2⊗Q1Mr,k2⋯Ik2⊗Qp−1Mr,k2xixj≜Mpxixji<j,where(29)Mp=JkMd,kp−1Q0Ik2⊗Q1Mr,k2⋯Ik2⊗Qp−1Mr,k2,Qs=Md,kM∨¯,kIk⊗M⊘k+sIk2⊗M∨¯,kIk⊗M⊘k−sMr,k2,s=0,1,⋯,p−1.
Furthermore,(30)xixj=Ed,kn−2xj+1⋯xnxi+1⋯xj−1x1⋯xi−1xixj=Ed,kn−jWkj,kn−jxi+1⋯xj−1x1⋯xi−1xixj⋯xn=Ed,kn−jWkj,kn−jWki,kj−1−ix1⋯xi−1xixi+1⋯xj−1xj⋯xn≜Mijx1x2⋯xni<j,∨s=0p−1yi∨¯⊘k+syj∨yi∨¯⊘k−syj=MpMijx=Mij,px,where x=x1x2⋯xn, Mij,p=MpMiji,j,=1,2,⋯,n,(31)Mij=Ed,kn−jWk2,kn−jEd,kj−1−iWk,kj−1−iEd,ki−1i<j,and the product is ∝”“.
Therefore,(32)∑i=1n∑j>iaij∨s=0p−1yi∨¯⊘k+syj∨yi∨¯⊘k−syj+bij∨s=0q−1yi∨¯⊘k+syj∨yi∨¯⊘k−syj,=∑i=1n∑j>iaijMij,p+bijMij,qx.
Thus, logical equations (19) are solved if and only if there exists x=δknv such that(33)∑i=1n∑j>iaijMij,p+bijMij,qx=Mx=0,that is, the v-th column of M is zero. Then, the proof is complete. □
Based on Theorem2, we give the following algorithm to find all for the Lp,q coloring solutions of the given graph.(34)S1,kn=δk1⋯1︸kn−12⋯2︸kn−1⋯k⋯k︸kn−1,S2,kn=δk1⋯1︸kn−22⋯2︸kn−2⋯k⋯k︸kn−21⋯1︸kn−22⋯2︸kn−2⋯k⋯k︸kn−2,⋮Sn,kn=δk12⋯k︸k⋯12⋯k︸k︸kn−1.
Using formula (24), compute xi=Si,knδknst and yi=k−1⋯10xi,i=1,2,⋯,n. Set(35)Sst=ffvi=yi,i=1,2,⋯,n.
Then, allLp,q-label coloring plans of G are Sstt=1,2,⋯,m.


## 4. Illustrative Example

In this section, we give an example to illustrate the effectiveness of the results/algorithms obtained in this paper.In order to avoid interference with each other, different channels need to be assigned to different base stations in the wireless network. Moreover, the main object of the channel allocation problem is to search an allocation scheme which has the channel as least as possible. Some mathematical models can be used to study the channel allocation problem of the wireless network, includingT-coloring, list coloring, set coloring, and Lp1,p2,⋯,pn-coloring. The most commonly used model is L2,1-coloring. Denote by GV,E the topological graph of the wireless network, where V is a node set denoting base stations or their users and E denotes an edge set. Now, we will use the L2,1-coloring model to analyze the channel allocation of the wireless network.Example 1.
Construct the telecommunication base stations among four cities denoted byA∼D, respectively. Denote a city by one vertex of the graph. If the base station constructed in city X can cover city Y, then there is an edge between X and Y. Now, the covering graph of base stations G=V,ℰ is established as shown in Figure 1. Our target is to search all schemes for channel allocation of the wireless network. In the wireless network, the channel interval is greater than or equal to 2 for two adjacent base stations and greater than or equal to 1 for two base stations with distance 2.
From Figure1, we have its adjacency matrix as the following:(36)A=0111100110011110.
According toA, we have by the above definition(37)B=0111101111011110.
Using Algorithm1, we can compute the matrix M defined in (26) by the semitensor product. Then, by Matlab, k=5 different channels which are denoted by 0, 1, 2, 3, and 4 are needed to satisfy the requirement in the channel allocation of the wireless network. Moreover, all detailed schemes are corresponding to(38)ColiM=0,i=97,117,221,241,385,405,509,529.The corresponding channel schemes are shown in Table 1.
For example, fori=97, y1=4,y2=1,y3=0,y4=3. That is, channels 4, 1, 0, and 3 are, respectively, assigned to stations A, B, C, and D which satisfies the requirement in the channel allocation of the wireless network. Moreover, from the table, there are at least 4 channels to satisfy the graph.Figure 1
A topological graph of the wireless network.Algorithm 1: Given a graph G with nodes V=v1,v2,…,vn, establish a logical function fvi=yi∈0,1,…,k−1 and let xi=δkk−yi, i=1,2,…,n. To determine all Lp,q-label coloring plans of G, we can do by the following steps:
(1)
Compute matrixM by (20).(2)
If there is no commonk such that ColkM=0, then G has no Lp,q-label coloring solution, and stop the calculation. Otherwise, find out the number s such that ColsM=0 and denote these by s1,s2,…,sm.(3)
For each indexs1,s2,…,sm, let ∝i=1nxi=δknst, t=1,2,…,m. Let [11]Table 1
Corresponding channel schemes.
i(y1, y2, y3, y4)(A, B, C, D)97(4, 1, 0, 3)(4, 1, 0, 3)117(4, 0, 1, 3)(4, 0, 1, 3)221(3, 1, 0, 4)(3, 1, 0, 4)241(3, 0, 1, 4)(3, 0, 1, 4)385(1, 4, 3, 0)(1, 4, 3, 0)405(1, 3, 4, 0)(1, 3, 4, 0)509(0, 4, 3, 1)(0, 4, 3, 1)529(0, 3, 4, 1)(0, 3, 4, 1)


## 5. Conclusion

TheLp,q-coloring problem of the graph is studied with application to channel allocation of the wireless network in this paper. The necessary and sufficient conditions for solving the Lp,q-coloring problem are given by introducing two new logical operators. Moreover, it is noted that all solutions of the obtained logical equations are corresponding to each coloring scheme. By using the semitensor product, the necessary and sufficient conditions are converted to an algebraic form. Based on this, all coloring schemes can be obtained through searching all column indices of the zero columns. Furthermore, an illustration example on channel allocation of the wireless network is given to show the effectiveness of the obtained results in this paper. In future, we plan to study other coloring problems by using the semitensor product method, i.e., T-coloring, list coloring, and set coloring.



---

*Source: 5369859-2020-06-03.xml*