GRAPH THEORY SEMINAR

• September 19, Futaba Okamoto: Measures of Traversability in Graphs
  
  
• September 26, Paul Miller: Pseudorandom Properties of Graphs (I)
  
  
• October 3, Ping Zhang: Radio Colorings of Graphs.
  

  Abstract:

  According to Federal Communications Commission (FCC) 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, Mary Radcliffe: Clock Lattices and Planar Graphs.
  
  

  Abstract:

  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, Ping Zhang: Rainbow Connection in Graphs.
  
  

  Abstract:

  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, Allen Schwenk: 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
  
  

  Abstract:

  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, Futaba Okamoto: A Tale of Two Numbers
  
  
• November 21, Paul Miller: Pseudorandom Properties of Graphs (II)
  
  
• November 28, Clifton Ealy: On the classification of some large classes of "regular" bipartite graphs
  
  

  Abstract:

  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.