Let
G
be a graph. For two vertices
u
and
v
in
G
, we denote
d
(
u
,
v
)
the distance between
u
and
v
. Let
j
,
k
be positive integers with
j
⩾
k
. An
L
(
j
,
k
)
-
labelling for
G
is a function
f
:
V
...(
G
)
→
{
0
,
1
,
2
,
…
}
such that for any two vertices
u
and
v
,
|
f
(
u
)
−
f
(
v
)
|
is at least
j
if
d
(
u
,
v
)
=
1
; and is at least
k
if
d
(
u
,
v
)
=
2
. The
span of
f
is the difference between the largest and the smallest numbers in
f
(
V
)
. The
λ
j
,
k
-
number for
G
, denoted by
λ
j
,
k
(
G
)
, is the minimum span over all
L
(
j
,
k
)
-labellings of
G
. We introduce a new parameter for a tree
T
, namely, the maximum ordering-degree, denoted by
M
(
T
)
. Combining this new parameter and the special family of infinite trees introduced by Chang and Lu (2003)
3, we present upper and lower bounds for
λ
j
,
k
(
T
)
in terms of
j
,
k
,
M
(
T
)
, and
Δ
(
T
)
(the maximum degree of
T
). For a special case when
j
⩾
Δ
(
T
)
k
, the upper and the lower bounds are
k
apart. Moreover, we completely determine
λ
j
,
k
(
T
)
for trees
T
with
j
⩾
M
(
T
)
k
.
An
L
(
j
,
k
)
-labeling of a graph is a vertex labeling such that the difference of the labels of any two adjacent vertices is at least
j
and that of any two vertices of distance
2
is at least
k
. ...The minimum span of all
L
(
j
,
k
)
-labelings of
G
is denoted by
λ
k
j
(
G
)
. Lin and Lam (Discret Math 308:3805–3815,
2008
) provided an upper bound of
λ
1
2
(
K
m
×
C
n
)
when
K
m
×
C
n
is the direct product of a complete graph
K
m
and a cycle
C
n
. And they found the exact value of
λ
1
2
(
K
m
×
C
n
)
for some
m
and
n
. In this paper, we obtain an upper bound and a lower bound of
λ
1
1
(
K
m
×
C
n
)
. As a consequence we compute
λ
1
1
(
K
m
×
C
n
)
when
n
is even or
n
≥
4
m
+
1
.
An L(2,1) labeling of a graph G is a vertex labeling such that any pair of vertices vi and vj must have labels at least 2 apart if d(vi,vj)=1 and labels at least 1 apart if d(vi,vj)=2. The span of an ...L(2,1) labeling f on a graph G is the maximum f(u) for all u∈V(G). The L(2,1) span of a graph G is the minimum span of all L(2,1) labelings on G. The L(2,1) labeling on trees has been extensively studied in recent years. In this paper we present a complete characterization of the L(2,1) span of trees up to twenty vertices.
A list channel assignment problem is a triple (G,L,w), where G is a graph, L is a function which assigns to each vertex of G a list of integers (colors), and w is a function which assigns to each ...edge of G a positive integer (its weight). A coloring c of the vertices of G is proper if c(v)\in L(v)$ for each vertex v and $|c(u)-c(v)|\ge w(uv)$ for each edge uv. A weighted degree $\deg_w(v)$ of a vertex v is the sum of the weights of the edges incident with v. If G is connected, $|L(v)|>\deg_w(v)$ for at least one v, and $|L(v)|\ge\deg_w(v)$ for all v, then a proper coloring always exists. A list channel assignment problem is balanced if $|L(v)|=\deg_w(v)$ for all v. We characterize all balanced list channel assignment problems (G,L,w) which admit a proper coloring. An application of this result is that each graph with maximum degree $\Delta\ge 2$ has an L(2,1)-labeling using integers $0,\ldots,\Delta^2+\Delta-1$.
Notes on and labelings for -cube Zhou, Haiying; Shiu, Wai Chee; Lam, Peter Che Bor
Journal of combinatorial optimization,
10/2014, Volume:
28, Issue:
3
Journal Article
Peer reviewed
Suppose
is a positive integer. An
-labeling of a simple graph
is a function
such that
if
; and
if
. The span of an
-labeling
is the absolute difference between the maximum and minimum labels. The
...-labeling number,
, is the minimum of span over all
-labelings of
. Whittlesey et al. proved that
where
and
. As a consequence,
for
. In particular,
. In this paper, we provide an elementary proof of this bound. Also, we study the
-labeling number of
. A lower bound on
are provided and
are determined.
Radio number of ladder graphs Wang, Haoli; Xu, Xirong; Yang, Yuansheng ...
International journal of computer mathematics,
07/2011, Volume:
88, Issue:
10
Journal Article
Peer reviewed
Let G be a connected graph with diameter diam(G). The radio number for G, denoted by rn(G), is the smallest integer k such that there exists a function f: V(G)→{0, 1, 2, ..., k} with the following ...satisfied for all vertices u and v:|f(u)−f(v)|≥diam (G)−d
G
(u, v)+1, where d
G
(u, v) is the distance between u and v in G. In this paper, we determine the radio number of ladder graphs.
PDF
