Transcript sample Powerpoint slides

Graph Labeling Problems
Appropriate for
Undergraduate Research
Research with Undergraduates Session
MathFest, 2009
Cindy Wyels
CSU Channel Islands
Overview

Distance labeling schemes

Radio labeling

Research with undergrads: context

Problems for undergraduate research

Radio numbers of graph families

Radio numbers and graph properties

Properties of radio numbers

Radio numbers and graph operations

Achievable radio numbers
Distance Labeling
Motivating Context: the Channel Assignment Problem
General Idea: geographically close transmitters must be
assigned channels with large frequency differences;
distant transmitters may be assigned channels with
relatively close frequencies.
Channel Assignment via Graphs
Model: vertices correspond to transmitters.
The distance between vertices u and v, d(u,v), is the length
of the shortest path between u and v.
d(u,v) = 3
u
d(w,v) = 4
w
diam(G) = 4
v
The diameter of the graph G, diam(G), is the longest
distance in the graph.
Defining Distance Labeling
All graph labeling starts with a function
f : V(G) → N
that satisfies some conditions.
1
v
3
3
f(v) = 3
2 3
f(w) = 1
1
w
1
5
Some distance labeling schemes
f : V(G) → N satisfies ______________
2 d
Ld(2,1): f (u )  f (v)  
d
when d (u , v)  1
when d (u , v)  2
k-labeling: d (u , v)  f (u )  f (v)  k  1 u , v  V (G )
Antipodal: d (u , v)  f (u )  f (v)  diam(G )
Radio:
(same)
d (u , v)  f (u )  f (v)  diam(G )  1 (same)
Radio:
d (u , v)  f (u )  f (v)  diam(G )  1
1
4
7
2
The radio number of a graph G, rn(G), is the
smallest integer m such that G has a radio labeling f
with m = max{f(v) | v in V(G)}.
4
1
6
rn(P4) = 6
3
Radio Numbers of Graph Families
Standard problem: find rn(G) for all graphs G
belonging to some family of graphs.
“… determining the radio number seems a difficult
problem even for some basic families of graphs.”
(Liu and Zhu)
 Complete graphs, wheels, stars (generally known)
S5
3
4
1
4
6
diam(Sn ) = 2
d (u , v)  f (u )  f (v)  3
5
rn(Sn) = n + 1
Radio Numbers of Graph Families
 Complete k-partite graphs (Chartrand, Erwin, Harary,
Zhang)
 Paths and cycles (Liu, Zhu)
 Squares of paths and cycles (Liu, Xie)
 Spiders (Liu)
Radio Numbers of Graph Families
 Gears (REU ’06)
 Products of cycles (REU ’06)
 Generalized prisms (REU ’06)
 Grids* (REU ’08)
 Ladders (REU ’08)
 Generalized gears* (REU ’09)
 Generalized wheels* (REU ’09)
 Unnamed families (REU ’09)
Radio Numbers & Graph Properties
 Diameter
 Girth
 Connectivity
 (your favorite set of graph properties)
Question: What can be said about the radio numbers of
graphs with these properties?
Radio Numbers & Graph Operations
E.g. products of graphs
The (box) product of graphs G and H, G □ H, is the
graph with vertex set V(G) × V(H),
where (g1, h1) is adjacent to (g2, h2) if and only if
g1 = g2 and h1 is adjacent to h2 (in H), and
h1 = h2 and g1 is adjacent to g2 (in G).
(a, 1)
1
a
b
3
(b, 3)
5
(b, 5)
(a, 5)
Graph Numbers and Box Products

Coloring: χ(G□H) = max{χ(G), χ(H)}

Graham’s Conjecture: π(G□H) ≤ π(G) ∙ π(H)

Optimal pebbling: g(G□H) ≤ g(G) ∙ g(H)
Question: Can rn(G □ H) be determined by rn(G)
and rn(H)? If not, what else is needed?
REU ’07 students at JMM
Bounds on radio numbers of products of graphs
REU ‘07 Results – Lower Bounds
Radio Numbers: rn(G □ H) ≥ rn(G) ∙ rn(H) - 2
Number of Vertices: rn(G □ H) ≥ |V(G)| ∙ |V(H)|
Gaps:
rn(G □ H) ≥ (½(|V(G)|∙|V(H)| - 1)(φ(G) - φ(H) – 2)
Analysis of Lower Bounds
Product
Radio No.
Vertices
Gap
C4 □ P2
5
8
–
Cn □ P2
n2/8
2n
–
C4 □ C4
8
16
30
Cn □ Cn
n2/4
n3/8
n2
P4 □ P4
10
16
30
9,800
10,000
499,902
Pn □ Pn
n2
n2
n3/4
Pete □ Pete
18
100
100
P100 □ P100
REU ‘07 Results – Upper Bounds
Theorem (REU ’07): Assume G and H are graphs
satisfying diam(G) - diam(H) ≥ 2 as well as
rn(G) = n and rn(H) = m. Then
rn(G □ H) ≤ diam(G)(n+m-2) + 2mn - 4n - 2m + 8.
REU ’07 proved two other theorems providing
upper bounds under different hypotheses.
Using Gaps
Need lemma giving M = max{d(u,v)+d(v,w)+d(w,v)}.
Assume f(u) < f(v) < f(w).
Summing the radio condition
d(u,v) + |f(u) - f(v)| ≥ diam(G) + 1
for each pair of vertices in {u, v, w} gives
M + 2f(w) – 2f(u) ≥ 3 diam(G) + 3
i.e.
f(w) – f(u) ≥ ½(3 diam(G) + 3 – M).
Using Gaps, cont.
Have f(w) – f(u) ≥ ½(3 diam(G) + 3 – M) = gap.
gap + 2
12
gap + 1
gap
2gap + 2
2gap + 1
gap
gap
n 1

n odd,
 gap  2  1
If |V(G)| = n, this yields rn(G )  
n 
 gap    1  2 n even.

2 
Using Gaps to Determine a Lower
Bound for the Radio Number of Prisms
 2
diam(Yn )  1  n
Y6
u
v
Choose any three vertices
u, v, and w.
w
d(u,v) + d(u,w) + d(v,w) ≤ 2∙diam(Yn) (n even)
Assume we have a radio labeling f of Yn, and
f(u) < f(v) < f(w). Then
d (u , v)  f (v)  f (u )  diam(Yn )  1
d (u, w)  f ( w)  f (u )  diam(Yn )  1
d (v, w)  f ( w)  f (v)  diam(Yn )  1
3 d (u , w)  2 f ( w)  2 f (u )  3 diam(Yn )  3
diam(Yn )  3
f ( w)  f (u ) 
2
Strategies for establishing an upper
bound for rn(G)
Define a labeling, prove it’s a radio labeling,
determine the maximum label.
Might use an intermediate labeling that orders
the vertices {x1, x2, … xs} so that f(xi) > f(xj) iff
i > j.
Using patterns, iteration, symmetry, etc. to
define a labeling makes it easier to prove it’s a
radio labeling.