Let be a simple connected graph with diameter d(G) and k be a positive integer. A radio k-labeling of G is a function such that holds for each pair of distinct vertices u and v of G, where is the ...distance between u and v in G. The absolute difference of the largest and smallest values in is termed as the span of f, and is denoted by The minimum span amongst all radio k-labelings of G is the radio k-chromatic number of G and it is denoted by In this article, we investigate a relationship between the radio k-chromatic number of an arbitrary graph and its square graph. This investigation leads us to the exact value of the radio number for square of graphs with small triameter.
For a simple connected graph
and a positive integer
with
, a radio
-coloring of
is a mapping
such that
holds for each pair of distinct vertices
and
of
, where
is the diameter of
and
is the distance ...between
and
in
. The span of a radio
-coloring
is the number
. The main aim of the radio
-coloring problem is to determine the minimum span of a radio
-coloring of
, denoted by
. Due to NP-hardness of this problem, people are finding lower bounds for
for particular families of graphs or general graphs
. In this article, we concentrate on finding upper bounds of radio
-chromatic number for general graphs and in consequence a coloring scheme depending on a partition of the vertex set
. We apply these bounds to cycle graph
and hypercube
and show that it is sharp when
is close to the diameter of these graphs.
For a simple connected graph
G
= (
V
(
G
),
E
(
G
)) and a positive integer
k
, a radio
k
-labelling of
G
is a mapping
f
:
V
(
G
)
→
{
0
,
1
,
2
,
…
}
such that
|
f
(
u
)
−
f
(
v
)
|
≥
k
+
1
−
d
(
u
...,
v
)
for each pair of distinct vertices
u
and
v
of
G
, where
d
(
u
,
v
) is the distance between
u
and
v
in
G
. The
radio k-chromatic number
is the minimum span of a radio
k
-labeling of
G
. In this article, we study the radio
k
-labelling problem for complete
m
-ary trees
T
m
,
h
and determine the exact value of radio
k
-chromatic number for these trees when
k
≥ 2
h
− 1.
Additional references listed for the article: Saha, Laxman and Basunia, Alamgir Rahaman (2020) "Radio Graceful Labelling of Graphs," Theory and Applications of Graphs: Vol. 7: Iss. 1, Article 7. DOI: ...10.20429/tag.2020.070107
Radio Graceful Labelling of Graphs Saha, Laxman
Theory and applications of graphs (Statesboro, Ga.),
05/2020, Volume:
7, Issue:
1
Journal Article
Peer reviewed
Open access
Radio labelling problem of graphs have their roots in communication problem known as \emph{Channel Assignment Problem}. For a simple connected graph $G=(V(G), E(G))$, a radio labeling is a mapping $f ...\colon V(G)\rightarrow \{0,1,2,\ldots\}$ such that $|f(u)-f(v)|\geq {\rm diam}(G)+1-d(u,v)$ for each pair of distinct vertices $u,v\in V(G)$, where $\rm{diam}(G)$ is the diameter of $G$ and $d(u,v)$ is the distance between $u$ and $v$. A radio labeling $f$ of a graph $G$ is a \emph{radio graceful labeling} of $G$ if $f(V(G)) = \{0,1,\ldots, |V(G)|-1\}$. A graph for which a radio graceful labeling exists is called \emph{radio graceful}. In this article, we study radio graceful labeling for general graphs in terms of some new parameters.
Metric Dimension of a simple connected graph is the minimum number of vertices those are used to identify each vertex of the graph uniquely using distance code. In this paper, we determine metric ...dimension of ideal-intersection graph for the ring where n being a positive integer.
PDF
