The channel assignment problem (CAP) which finds an efficient assignment of channels to the transmitters of a wireless network is applicable to cellular mobile system (CMS). There are lots of results ...on CAP for CMS where the channel separation constraint is represented by a symmetric matrix or a graph. In particular, the Philadelphia instances and the 49-cell system are benchmark CAP for CMS and are treated in many papers. The distance multi-labelling (DM) problem on a graph with weighted vertices is an effective mathematical model of CAP for CMS in which a CMS is represented by a graph with weighted vertices, where a vertex corresponds to a cell with the number of calls on it as its weight. A DM on a graph with weighted vertices is an assignment of a set of non-negative numbers to each vertex. These numbers, which are called labels, represent the channels assigned to the demand calls in each cell. DM is a generalisation of both distance labelling and graph multi-colouring. In this study, the author introduce a new method called the layering method to find a DM on a graph with weighted vertices. Using this method, we obtain optimal DM for two Philadelphia instances. For each of them, the authors obtain a DM according to the range of separation conditions, and it includes known optimal results which are individually obtained under one separation condition.
List backbone colouring of graphs Bu, Yuehua; Finbow, Stephen; Liu, Daphne Der-Fen ...
Discrete Applied Mathematics,
04/2014, Volume:
167
Journal Article
Peer reviewed
Open access
Suppose that G is a graph and that H is a subgraph of G. Let L be a mapping that assigns to each vertex v of G a set L(v) of positive integers. We say that (G,H) is backboneL-colourable if there is a ...proper vertex colouring c of G such that c(v)∈L(v) for all v∈V, and |c(u)−c(v)|⩾2 for every edge uv in H. We say that (G,H) is backbone k-choosable if (G,H) is backbone L-colourable for any list assignment L with |L(v)|=k for all v∈V(G). The backbone choice number of (G,H), denoted by chBB(G,H), is the minimum k such that (G,H) is backbone k-choosable. The concept of a backbone choice number is a generalization of both the choice number and the L(2,1)-choice number. Precisely, if E(H)=0̸, then chBB(G,H)=ch(G), where ch(G) is the choice number of G; if G=H2, then chBB(G,H) is the same as the L(2,1)-choice number of H. In this article, we first show that, if |L(v)|=dG(v)+2dH(v), then (G,H) is L-colourable, unless E(H)=0̸ and each block of G is a complete graph or an odd cycle. This generalizes a result of Erdős, Rubin, and Taylor on degree-choosable graphs. Second, we prove that chBB(G,H)⩽max{⌊mad(G)⌋+1,⌊mad(G)+2mad(H)⌋}, where mad(G) is the maximum average degree of a graph G. Finally, we establish various upper bounds on chBB(G,H) in terms of ch(G). In particular, we prove that, for a k-choosable graph G, chBB(G,H)⩽3k if every component of H is unicyclic; chBB(G,H)⩽2k if H is a matching; and chBB(G,H)⩽2k+1 if H is a disjoint union of paths with length at most 2.
Given a graph G=(V,E), an L(δ1,δ2,δ3)-labeling is a function f assigning to nodes of V colors from a set {0,1,…,kf} such that |f(u)−f(v)|⩾δi if u and v are at distance i in G. The aim of the ...L(δ1,δ2,δ3)-labeling problem consists in finding a coloring function f such that the value of kf is minimum. This minimum value is called λδ1,δ2,δ3(G).
In this paper we study this problem on the eight-regular grids for the special values (δ1,δ2,δ3)=(3,2,1) and (δ1,δ2,δ3)=(2,1,1), providing optimal labelings. Furthermore, exploiting the lower bound technique, we improve the known lower bound on λ3,2,1 for triangular grids.
•Optimal L(3,2,1)-labeling for ERGs.•Optimal L(2,1,1)-labeling for ERGs.•Improved lower bound on the λ3,2,1-number for triangular grids.
An
L
(2, 1)-labeling for a graph
G
=
(
V
,
E
)
is a function
f
on
V
such that
|
f
(
u
)
-
f
(
v
)
|
≥
2
if
u
and
v
are adjacent and
f
(
u
) and
f
(
v
) are distinct if
u
and
v
are vertices of ...distance two. The
L
(2, 1)-labeling number, or the lambda number
λ
(
G
)
, for
G
is the minimum span over all
L
(2, 1)-labelings of
G
. When
P
m
×
C
n
is the direct product of a path
P
m
and a cycle
C
n
, Jha et al. (Discret Appl Math 145:317–325,
2005
) computed the lambda number of
P
m
×
C
n
for
n
≥
3
and
m
=
4
,
5
. They also showed that when
m
≥
6
and
n
≥
7
,
λ
(
P
m
×
C
n
)
=
6
if and only if
n
is the multiple of 7 and conjectured that it is 7 if otherwise. They also showed that
λ
(
C
7
i
×
C
7
j
)
=
6
for some
i
,
j
. In this paper, we show that when
m
≥
6
and
n
≥
3
,
λ
(
P
m
×
C
n
)
=
7
if and only if
n
is not a multiple of 7. Consequently the conjecture is proved. Here we also provide the conditions on
m
and
n
such that
λ
(
C
m
×
C
n
)
≤
7
.
This paper considers the channel assignment problem in mobile communications systems. Suppose there are many base stations in an area, each of which demands a number of channels to transmit signals. ...The channels assigned to the same base station must be separated in some extension, and two channels assigned to two different stations that are within a distance must be separated in some other extension according to the distance between the two stations. The aim is to assign channels to stations so that the interference is controlled within an acceptable level and the spectrum of channels used is minimized. This channel assignment problem can be modeled as the multiple
t
-separated
L
(
j
1
,
j
2
,
…
,
j
m
)
-labeling of the interference graph. In this paper, we consider the case when all base stations demand the same number of channels. This case is referred as
n
-fold
t
-separated
L
(
j
1
,
j
2
,
…
,
j
m
)
-labeling of a graph. This paper first investigates the basic properties of
n
-fold
t
-separated
L
(
j
1
,
j
2
,
…
,
j
m
)
-labelings of graphs. And then it focuses on the special case when
m
=
1
. The optimal
n
-fold
t
-separated
L
(
j
)-labelings of all complete graphs and almost all cycles are constructed. As a consequence, the optimal
n
-fold
t
-separated
L
(
j
1
,
j
2
,
…
,
j
m
)
-labelings of the triangular lattice and the square lattice are obtained for the case
j
1
=
j
2
=
⋯
=
j
m
. This provides an optimal solution to the corresponding channel assignment problems with interference graphs being the triangular lattice and the square lattice, in which each base station demands a set of
n
channels that are
t
-separated and channels from two different stations at distance at most
m
must be
j
1
-separated. We also study a variation of
n
-fold
t
-separated
L
(
j
1
,
j
2
,
…
,
j
m
)
-labeling, namely,
n
-fold
t
-separated consecutive
L
(
j
1
,
j
2
,
…
,
j
m
)
-labeling. And present the optimal
n
-fold
t
-separated consecutive
L
(
j
)-labelings of all complete graphs and cycles.
For a simple connected graph G and an integer k with 1⩽k⩽ diam(G), a radio k-coloring of G is an assignment f of non-negative integers to the vertices of G such that |f(u)−f(v)|⩾k+1−d(u,v) for each ...pair of distinct vertices u and v of G, where diam(G) is the diameter of G and d(u,v) is the distance between u and v in G. The span of a radio k-coloring f is the largest integer assigned by f to a vertex of G, and the radiok-chromatic number of G, denoted by rck(G), is the minimum of spans of all possible radio k-colorings of G. If k=diam(G)−1, then rck(G) is known as the antipodal number of G. In this paper, we give an upper and a lower bound of rck(Cnr) for all possible values of n, k and r. Also we show that these bounds are sharp for antipodal number of Cnr for several values of n and r.
Let
G
=
(
V
,
E
)
be a graph. For two vertices
u
and
v
in
G
, we denote
d
G
(
u
,
v
)
the distance between
u
and
v
. A vertex
v
is called an
i
-neighbor of
u
if
d
G
(
u
,
v
)
=
i
. Let
s
,
t
and
k
be ...nonnegative integers. An (
s
,
t
)-relaxed
k
-
L
(2, 1)-labeling of a graph
G
is an assignment of labels from
{
0
,
1
,
…
,
k
}
to the vertices of
G
if the following three conditions are met: (1) adjacent vertices get different labels; (2) for any vertex
u
of
G
, there are at most
s
1-neighbors of
u
receiving labels from
{
f
(
u
)
-
1
,
f
(
u
)
+
1
}
; (3) for any vertex
u
of
G
, the number of 2-neighbors of
u
assigned the label
f
(
u
) is at most
t
. The (
s
,
t
)-relaxed
L
(2, 1)-labeling number
λ
2
,
1
s
,
t
(
G
)
of
G
is the minimum
k
such that
G
admits an (
s
,
t
)-relaxed
k
-
L
(2, 1)-labeling. In this article, we refute Conjecture 4 and Conjecture 5 stated in (Lin in J Comb Optim. doi:
10.1007/s10878-014-9746-9
,
2013
).
A multilevel distance labeling of a graph
G
=
(
V
,
E
)
is a function
f
on
V
into
N
∪
{
0
}
such that
|
f
(
v
)
-
f
(
w
)
|
≥
diam
(
G
)
+
1
-
dist
(
v
,
w
)
for all
v
,
w
∈
V
. The radio number
rn
(
...G
)
of
G
is the minimum span over all multilevel distance labelings of
G
. In this paper, we completely determine the radio number
rn
(
G
)
of
G
where
G
is the Cartesian product of a path
P
n
with
n
(
n
≥
4
)
vertices and a complete graph
K
m
with
m
(
m
≥
3
)
vertices.
L(h, k)-labelling for octagonal grid Kim, Byeong Moon; Rho, Yoomi; Song, Byung Chul
International journal of computer mathematics,
11/2015, Volume:
92, Issue:
11
Journal Article
Peer reviewed
An
-labelling of a graph G is an assignment of nonnegative integers, called labels, to the vertices of G such that two adjacent vertices receive labels that differ by at least h and those of distance ...two receive labels that differ by at least k. Among the span of all
-labellings of G,
is the smallest one. In this paper for the octagonal grid
, we show that the upper bound for
is
when
. And when
, we show that
.
PDF
