GRAPH THEORY SEMINAR
SCHEDULE (Fall 2006)
Tuesday 1:00-1:50 pm, Alavi
- September 19,
Measures of Traversability in Graphs
- September 26,
Pseudorandom Properties of Graphs (I)
- October 3,
Ping Zhang: Radio Colorings of Graphs.
According to Federal Communications
regulations, FM radio stations located within
a certain proximity of one another must be assigned distinct channels,
and the nearer two stations are to each other, the greater the differences
in their assigned channels must be. The problem of
obtaining an optimal assignment of channels to a specified
set of radio transmitters according to some prescribed
restrictions on the distances between transmitters as well
as other factors, including its effective radiated power and
antenna height, is referred to as the Channel Assignment Problem.
Inspired by this problem, we define a radio coloring of a
connected graph. Results and open questions from this area of
research will be presented.
- October 10,
Clock Lattices and Planar Graphs.
An important problem in Knot Theory involves
the search for and calculation of various knot polynomials.
Several such polynomials involve the computation of lattices
on the knot. In particular Lou Kaufman defines a lattice
structure on the set of spanning trees of a plane embedded
multigraph (the medial graph of a knot), called the clock lattice.
We examine the construction of the clock lattice and the
effect of some graph operations on the clock lattice,
as well as open problems in the topic of clock lattices.
- October 17,
Rainbow Connection in Graphs.
Let G be a nontrivial connected graph on which is defined
an edge coloring of G, where adjacent edges may be
colored the same. A path P in G is a rainbow path if no
two edges of P are colored the same. The graph G is rainbow-connected
if every two vertices of G are connected by a rainbow path.
The minimum integer k for which there exists a k-edge coloring
of a graph G such that G is rainbow-connected
is referred to as the rainbow connection number of G.
If every two vertices of G are connected by a rainbow geodesic, then
G is strongly rainbow-connected. Results and open questions from
this area of research will be presented.
- October 24,
Do k consecutive natural numbers always include one that
is relatively prime to all the others?
- October 31,
Clifton Ealy: Some remarks on Expander Graphs
In the October 2006 issue of "The Bulletin of the AMS",
there is an over 200 page survey article on Expander Graphs.
In this talk, I will discuss applications of expander graphs
and a basic example. Time permitting, I will indicate
some possible new ways of finding expander graphs.
- November 7,
A Tale of Two Numbers
- November 21,
Pseudorandom Properties of Graphs (II)
- November 28,
On the classification of some large
classes of "regular" bipartite graphs
Recently, J. Tits and R. Weiss classified a
large class of regular bipartite graphs.
Their work was preceded by an earlier
classification due to E. Shult in an attempt to know
"when a graph coul.d be a thick bipartite graph of
diameter 4 and girth 8. The above efforts were all
based on the fundamental result of G. Higman and W. Feit.
In this talk, I will survey these efforts.