Transcript V - California State University Channel Islands

Graphs: Graceful, Equitable
and Distance Labelings
Cindy Wyels
California State University Channel Islands
Graph theory Ideas for Undergraduate Research
MAA Invited Paper Session at MathFest, 2006
Organizer: Aparna Higgins, University of Dayton
Marc
América
Christina
Overview

Labeling schemes
•
•

Distance labeling
schemes
Graceful and kequitable labeling
Paul
Aaron
Juan
Advantages for undergraduate research
•
•
•
Low faculty and student start-up “costs”
Lots of accessible open problems
Can “get hands dirty” quickly
URL for slides provided at end.
Distance Labeling Schemes
Motivating Context: assignment
of channels to FM radio stations
General Idea: transmitters that are geographically close must
be assigned channels with large frequency differences;
transmitters that are further apart may receive channels with
relatively close frequencies.
Model: vertices correspond to transmitters; use usual graph
distance.
Some distance labeling schemes
f : V(G) → N satisfies ______________
Ld(2,1):
2d
f (u )  f (v)  
d
when d (u, v)  1
when d (u, v)  2
Ld(3,2,1), L(h,k), L(λ1, …λk): analogous
Radio: d (u, v)  f (u)  f (v)  diam (G)  1 u, v V (G)
Antipodal: d (u, v)  f (u)  f (v)  diam (G)
k-labeling:
d (u, v)  f (u)  f (v)  k  1
(same)
(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 max{f(v) | v in V(G)} = m.
4
1
6
rn(P4) = 6.
3
Good problem: find rn(G) for all graphs G
belonging to some graph family
“… determining the radio number seems a difficult
problem even for some basic families of graphs.”
(Liu and Zhu)

Complete k-partite graphs (Chartrand, Erwin, Harary,
Zhang)

Paths and cycles (Liu, Zhu)

Squares of paths and cycles (Liu, Xie)

Spiders (Liu, submitted)
Undergraduate Contributions

Complete graphs, complete bipartite
graphs, wheels

Gear graphs

Generalized prism graphs

Products of cycles
Strategies for establishing a lower
bound for rn(G)


Counting “forbidden values” (e.g. bipartite
graphs, wheels, gears)
Using “gaps” (vertex-transitive graphs)
Counting Forbidden Values
d(u,v)+ | f(u)-f(v) | ≥ 5
w
z
G7
v
Vertex
type
Minimum
label diff
Min. # of
forbidden
values
# of values
used as
labels
z
3
2
1
w
v
1
0
n
2
1
1
v
2
2(n -1)
n -1
Total: 2n +1
 rn(Gn )  4n  2 for n  4.
2n +1
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 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 
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.
Using an intermediate labeling
G8
w2
v1
x5
w1
v2
x9
x1
x10
v8
x16
w3
w8
x2
x8
v3
v7
x11
x15
z
w4
w7
v6
v4
w5
v5
w6
x0
x6
x4
x14
x12
x3
x13
1
i0


f ( xi )  
3i
1 i  n
2  n  3(i  n) n  1  i  2n

x7
Using patterns, iteration, etc. to prove
the labeling is a radio labeling




For products of cycles and for generalized
prism graphs, the gap was about half the
diameter.
This gives | f(xi) – f(xj) | ≥ diam(G) + 1
whenever j – i ≥ 4.
Also, | f(xi) – f(xj) | = | f(xi+k) – f(xj+k) |, so it
suffices to show the radio condition holds for
{x1, x2, x3, x4}.
Using symmetry in labeling also advantageous.
Some Radio Labeling Questions

Find relationships between rn(G) and specific graph
properties (e.g. connectivity, diameter, etc.).

Investigate radio numbers of various product graphs,
and/or determine the relationship between the radio
number of a product graph and the radio numbers of its
factor graphs.

Investigate radio numbers of powers of graphs.

Determine properties of minimal labelings. E.g. is the
radio number always realized by a labeling that assigns
1 to a cut vertex? … to a vertex of highest degree?

Create an algorithm for checking labelings.
Find radio numbers of families of graphs

Generalized gears (adapt
methods)

Ladders

Web graphs (products of cycles
and paths)

Products of cycles of different
sizes

Grid graphs (products of paths)

More generalized prisms
L(3,2,1) labeling
Clipperton, Gehrtz, Szaniszlo,
and Torkornoo (2006) provide the
L(3,2,1)-labeling numbers for:
undergraduates
- Complete graphs - Complete bipartite graphs
- Paths
- Cycles
- Caterpillars
- n-ary trees
They also give an upper bound for the L(3,2,1)-labeling
number in terms of the maximum degree of the graph.
Graceful and k-equitable labelings
•
Define a labeling f : V(G) → {0, 1, … |E(G)|}.
•
Edge (u,v) receives the label induced by | f(u) – f(v) |.
The labeling is graceful when none of the vertex or
edge labels repeat.
•
3
2
1
1
3
0
2
4
4
5
5
Graceful and k-equitable labelings
Define a labeling f : V(G) → {0, 1, … k-1}.
• Edge (u,v) receives the label induced by | f(u) – f(v) |.
• Let #Vj and #Ej be the number of vertices and edges,
respectively, labeled j.
• The labeling is k-equitable if |#Vi - #Vj| ≤ 1 and
|#Ei - #Ej| ≤ 1 for all i ≠ j in {0, 1, … k-1}.
•
k = 3:
0
2
2
#V0 = #V1 = #V2 = 2
1
1
1
0
2
1
0
2
#E0+1 = #E1 = #E2 = 2
What’s known?
graceful








Stars
Paths
Caterpillars
The Petersen graph
n-cycles for n ≡ 0, 3 (4)
Symmetric trees
All trees with no more
than four leaves
All trees with no more
than 27 vertices
k-equitable








Stars
Paths
Caterpillars
Eulerian graphs (conditions)
Cycles (conditions)
Wheels (k = 3)
All trees are 3-equitable.
All trees with fewer than five
leaves are k-equit.
Some Graceful/ k-Equitable Questions

Investigate particular types of trees to
determine whether they are k-equitable.
(E.g. complete binary trees are currently
under investigation.)

Explore whether particular families of
graphs are k-equitable or graceful.

Investigate whether methods of “gluing”
graceful trees together to form larger
graceful trees extend to k-equitability.
Reading to get started

Radio labeling: Chartrand, Erwin, Harary, and Zhang, Radio
labelings of graphs, Bull. Inst. Combin. Appl., 33 (2001), 7785.

L(2,1) labeling: Griggs & Yeh, Labeling graphs with a
condition at distance 2, SIAM J. Disc. Math., 5 (1992), 586595.

Graceful & k-equitable labeling: Cahit, Equitable Tree
Labellings, Ars. Combin. 40 (1995), 279-286.

General survey: Gallian, A dynamic survey of graph labeling,
Dynamical Surveys, DS6, Electron. J. Combin. (1998).
URL for these slides: http://faculty.csuci.edu/cynthia.wyels
Conjectures
Graceful labelings were defined in the context of graph
decompositions.
Rosa’s Th’m: If a tree T with m edges has a graceful
labeling, then K2m+1 decomposes into 2m+1 copies of T.
(1968)


Kotzig-Ringel Conj: Every tree has a graceful labeling.

Cahit’s Conj: All trees are k-equitable. (1990)
Are all complete-binary trees k-equitable?
Know true for k = 2^n, n = 0, 1, …, 5. Think method
extends to all n.
Know true for k = 2, 3, 4, 5, 6, 7.
Need last step to show true for all k congruent to 0, 1 mod
4.
Why worry about complete binary trees? Would like to
generalize any findings and methods.
All trees are 3-equitable
Outline how this was done. Emphasize student
contributions!
Rosa’s Th’m: If a tree T with m edges has a graceful
labeling, then K2m+1 decomposes into 2m+1 copies of T.


Kotzig-Ringel Conj: Every tree has a graceful labeling.

Cahit’s Conj: All trees are k-equitable.