Transcript PowerPoint Presentation - Radio Number for

Radio Numbers for
Square Paths & Cycles
This project is supported by the National Science Foundation (NSF)
under grant DMS-0302456
Daphne Liu & Melanie Xie
California State University, Los Angeles
Department of Mathematics
• Motivation & Definitions
• Previous Known Results
• New Results
• References
Copyright (c) by Daphne
Liu and Melanie Xie
Channel Assignment Problem?
• Motivation:
This vertex coloring problem is motivated by the
Channel Assignment Problem which is introduced by
Hale in 1980. In this problem, several radio stations
(or transmitters) are given. We want to assign to
each station a non-negative integers as channels so
that the interference is avoided. The closer the two
station are, the stronger the interference. Hence,
the closer the two stations, the larger the separation
of channels.
• Goal:
1. To assign channels for a set of radio stations to
prevent the interference between radio channels.
2. To minimized the span of channels.
Definitions



A graph G=(V,E) consists of two sets, V and E,
called vertex-set and edge-set, respectively.
Elements of V are called vertices.
Elements of E are called edges.

The distance a graph G, denoted by d(u,v),
between two vertices u and v in is the length
of a shortest path from u to v.

The diameter a graph G, denoted by diam(G),
is the maximum distance between a pair of
vertices.
u
v
d(u,w) = 2
z
w
y
x
diam(C6)= 3
Radio Labeling
Given G=(V, E), a radio k-labeling is a function

f : V  {0, 1, 2, ..., k}
so that for any two vertices u and v,
| f (u )  f (v) |  diam(G) - d(u, v)  1
Example:
diam(P5)=4
0
4
8
12
16
10
5
0
8
3
Radio Number

For a simple graph G, the radio number of G,
denoted by rn(G), is the minimum k of a radio
k-labeling of G.
Example:
7
diam(G) = 3
2
0
3
5
rn(G) = 7 (Chartrand et al. [2002])