GRAPH THEORY SEMINAR

• November 27 Ben Phillips: The Fundamental Group of a Graph
  

  Abstract: The fundamental group is a much studied topic in elementary topology. As graphs are also topological spaces, we shall investigate the fundamental group structure of an arbitrary graph G. In particular, the fundamental group of a graph is a free group. We shall also discuss some connections between the fundamental group of a graph and the genus of the graph.

  ---

• November 13 Clifton Ealy: Cages and Cayley Graphs
  

  Abstract: A (k,g)-cage is a regular graph of valence k and girth g with vertex set of least order. A Cayley graph is a graph which has a regular group of automorphisms. In this talk, we will discuss the following result: (##) (Alain Bretto and Luc Gillibert) For p a prime number greater or equal to 5, we have a regular graph of degree p, of girth 6, and with an order equal to 2xp2. Hence if G is a c(p,6)-cage, the order of V is bounded by 2xp2.

  ---

• November 6 Clifton Ealy: Cages

  ---

• October 30 Gary Chartrand: The 4-color Problem, A Look Back
  

  Abstract: The 4-color Problem, A Look Back.

  ---

• October 23 Ping Zhang: A Four Colorings Theorem
  

  Abstract: The most famous and most studied graph coloring number is the chromatic number. If the chromatic number of a graph G is k, then each k-coloring of G has three properties that give rise to three additional colorings of G. Relationships among these four colorings are studied.

  ---

• October 16 Allan Bickle: T-colorings and the Channel Assignment Problem
  

  Abstract: The Channel Assignment Problem is the problem of how to assign channels to transmitters that interfere with each other in some way. This situation can be modeled uning graph theory, with edges reperesenting the interference between transmitters. T-coloring can be used to address this problem. We will determine the minimum number of channels required, and how this relates to proper colorings. We will also address the question of how large the range of the channels used must be.

  ---

• October 2 Allen Schwenk: Using Eigenvalues to Search for Regular Graphs of Girth 5
  

  Abstract: Hoffman and Singleton identified those values of r for which there can exist an r-regular graph of girth 5 and order r2 + 1, namely r = 2, 3, 7, and possibly 57. Possibly 57? What does that mean? Will Brown showed that there are no r-regular graphs of girth 5 and order r2 + 2. We consider r-regular graphs of girth 5 and order r2 + 3. Using eigenvalue methods and Maple to factor large polynomials, we show the nonexistence of such graphs for r between 5 and 11 (inclusive). Similarly, no r-regular graphs of girth 7 and order r3 - r2 + r + 1 exist. On the other side, we give a simple construction for the Robertson graph of order 19 with r = 4, some graphs with order 20 and r = 4, and for two graphs of order 12 with r = 3.

  ---

• September 25, Allen Schwenk: Fundamentals of Eigenvalues and Graphs
  

  Abstract: What kind of eigenvalues does a connected graph have? What do eigenvectors look like? What kind of basis do we get? What is the Raleigh Quotient? What do the largest and smallest eigenvalues tell us? When is the average degree an eigenvalue? The maximum degree? In a connected graph, why is the largest eigenvalue always simple? What are the eigenvalues of complete graphs, complete graphs, cycle, and paths?

  ---

• September 18, Ben Phillips: The Garden of Eden Problem
  

  Abstract: Let G and H be graphs. We define the "offspring" product to be the graph obtained by orienting H and then replacing each arc with a copy of G, in a specified manner. This produces a new graph, which has an obvious edge composition into copies of G. The main issues to be addressed concern whether or not this obvious decomposition is unique. We shall discuss various results towards this end, as well as a connection to a certain NP completeness problem.

  ---

• September 11, A. T. White: 3-maps
  

  Abstract: Starting wih a simple observation about one conventional die, we (David Craft and I) extend to the three cubic dice based upon the platonic solids and then to cubic maps in general. We take special interest when a 3-region coloring exists, for then 3's abound: we find a 3-edge coloring of a special sort, and also three partitions of the vertex set of the cubic graph which lead to various topological constructions.

  ---