GRAPH THEORY SEMINAR

• September 12 Organizational meeting
  
  Ping Zhang: Hamiltonian Walks in Graphs
  

  Abstract: In 1973 Goodman and Hedetniemi introduced the concept of a Hamiltonian walk in a connected graph, defined as a closed spanning walk of minimum length in the graph. During the 10-year period 1973-83, this concept received considerable attention. In 2003, we introduced an alternative way to look at this concept. This new approach brought renewed interest in this topic and has resulted in increased research on this subject. We discuss some recent results obtained in this area.

  ---

• September 19 Gary Chartrand: Digraphs
  

  Abstract: Three classes of digraphs will be discussed, along with some stories, problems and theorems associated with these classes.

  ---

• September 26 Daniel Johnston: A Bichromatic View of Matching and Domination
  

  Abstract: A red-blue coloring of a graph G is an edge coloring of G in which every edge is colored red or blue. Let F be a connected graph of size 2 or more with a red-blue coloring, at least one edge of each color, where some blue edge of F is designated as the root of F. Such an edge-colored graph F is called a color frame. An F-coloring of a graph G is a red-blue coloring of G in which every blue edge of G is the root edge of a copy of F in G. The F-chromatic index of G is the minimum number of red edges in an F-coloring of G. We show that these concepts generalize both edge domination and matchings in graphs.

  ---

• October 3 Eric Andrews: Some Topics Eulerian
  

  Abstract: A closed walk in a connected graph G that contains every edge of G exactly once is an Eulerian circuit. A graph is Eulerian if it contains an Eulerian circuit. It is well known that a connected graph G is Eulerian if and only if every vertex of G is even. It is also known that a connected graph with 2k odd vertices can be decomposed into k open trails, at most one of which has odd length. We present a generalization of this result. An Eulerian walk in a connected graph G is a closed walk that contains every edge of G at least once. We discuss Eulerian walks with some prescribed properties.

  ---

• October 17 Art White: The Greatly Generalized Euler Identity (for graph imbeddings)
  

  Abstract: From p - q + r = 2 for connected planar graphs, the generalization to p - q + r = 2 - 2k for 2-cell imbeddings (of necessarily connected graphs) on S(k) is well-known. Recently Ed Schmeichel (of San Jose State University) has further extended to the following theorem: If a graph is imbedded on S(k), then p - q + r = 2 - 2k + (summation over regions R) (2g(R) + h(R) - 1). We discuss this all-inclusive generalization.

  ---

• October 24 Eric Andrews: On Eulerian Walks in Graphs --- Doctoral Dissertation Proposal
  

  ---

• October 31 Andrzej Dudek: On restricted Ramsey numbers
  

  Abstract: A classical Ramsey theorem states that in any 2-coloring of the edges of a sufficiently large complete graph, one will always find a monochromatic complete subgraph. In 1970, Folkman extended this result showing that for any graph G there exists a graph H with the same clique number as G such that any 2-coloring of the edges of H yields a monochromatic copy of G. In this talk, we present some old and recent developments concerning Folkman-type results.

  ---

• November 7 Laars Helenius: Tree Counting in Biclique Decompositions
  

  ---

• November 14 John Engbers (Ph.D. student at Notre Dame): Extremal Questions for H-Colorings
  

  Abstract: An H-coloring of a finite, simple graph G is a map from the vertices of G to the vertices of a finite graph H (without multiple edges, but possibly with loops) that preserves edge adjacency. H-colorings generalize many important graph theoretic notions, such as proper q-colorings (via H = K_{q}) and independent sets (via H as an edge with a loop on one endvertex). We will consider the following extremal question: given a family of graphs G which graph in the family has the largest number H-colorings for a given H? We present several recent results for G(n,\delta), the family of graphs on n vertices with minimum degree \delta.

  ---

• November 28 Allen Schwenk: Hamiltonian Decomposable Line Graphs
  

  ---

Previous Graph Theory Seminars