A lower bound for the radio number of graphs

DOI10.1007/978-3-030-11509-8_14MaRDI QIDQ6315548arXivFDO

Publication date 13 March 2019

Graph operations (line graphs, products, etc.) (05C76) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: A radio labeling of a graph

G

is a mapping

v p : V (G) i g h t a r r o w 0, 1, 2, ...

such that

| v p (u) - v p (v) | g e q d i a m (G) + 1 - d (u, v)

for every pair of distinct vertices

u, v

of

G

, where

d i a m (G)

and

d (u, v)

are the diameter of

G

and distance between

u

and

v

in

G

, respectively. The radio number

n (G)

of

G

is the smallest number

k

such that

G

has radio labeling with

m a x v p (v) : v i n V (G)

=

k

. In this paper, we slightly improve the lower bound for the radio number of graphs given by Das emph{et al.} in [5] and, give necessary and sufficient condition to achieve the lower bound. Using this result, we determine the radio number for cartesian product of paths

P_{n}

and the Peterson graph

P

. We give a short proof for the radio number of cartesian product of paths

P_{n}

and complete graphs

K_{m}

given by Kim emph{et al.} in [6].

This page was built for publication: A lower bound for the radio number of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6315548)