GRAPH THEORY SEMINAR

---

• September 9 Organizational meeting
  

  ---

• September 16 Art White Petrie Maps
  

  ---

• September 23 Ping Zhang: Rainbow Colorings and Rainbow Connectivity of Graphs
  

  Abstract: Let G be an edge-colored graph 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. Generalizations of these concepts are introduced.

  ---

• September 30 John Kusku: Steinitz's Theorem of Convex Types
  

  Abstract: Steinitz's Theorem states that a graph G is isomorphic to the 1-dimensional skeleton of a polytope if and only if G is planar and 3-connected. We will strive to understand a proof of this theorem.

  ---

• October 7 Willem Renzema: Hamiltonian Labelings of Graphs
  

  Abstract: A Hamiltonian labeling of a graph G of order n is a vertex labeling c for which the sum of |c(u) - c(v)| and the length of a longest u-v path in G is at least n for every pair u, v of two distinct vertices in G. We investigate the minimum k for which G has a Hamiltonian labeling, all labels of which belong to the set {1, 2, ..., k}. Some results involving this concept are described.

  ---

• October 14 Gary Chartrand: Reflections on Colorings
  

  Abstract: We take a new look at vertex colorings for graphs.

  ---

• October 28 Allan Bickle The k-core of a Graph (Part 1)
  

  ---

• November 11 Allen Schwenk Minimum sets with no n terms that sum to zero
  

  ---

• November 18 Linda Lesniak: Interconnection Networks and Matching Preclusion Numbers
  

  Abstract: The n-cube is the classic example of an interconnection network. A number of such networks have been considered in the past few years which have been called "natural extensions of the cube."
  The matching preclusion number of a graph is the minimum number of edges whose removal results in a graph with no perfect matching or almost perfect matching. Matching preclusion numbers are determined for a sequence of interconnection networks.

  ---

• November 25 Ben Phillips: Straight line embeddings of planar graphs with integer edge length
  

  Abstract: A straight line embedding of a graph G = (V, E) is an injective function f from V to the plane such that for any two distinct edges ab, cd in E the the line segments (f(a), f(b)) and (f(c), f(d)) are internally disjoint. It is a well known result that every planar graph admits a straight line embedding. We shall consider a further restriction of this idea, where the edges in the embedding have integral Euclidean distance. We shall discuss some recent work of Geelen, Anjie, and McKinnon, as well as some basic examples.

  ---

• December 2 Allan Bickle: The k-core of a Graph (Part 2)
  

  Abstract: The k-core of a graph can be defined as the maximal subgraph of a graph G that has minimum degree > = k. We will examine results about the k-core and diameter, genus, and graphs produced from one or two other graphs.