Sarmad Abbasi, Rutgers University
"Spanning Cycles in Dense Graphs"A conjecture of ElZahar asserts that if G is a graph on n = n_1+ n_2 + ... n_r vertices with minimum degree at least \sum_{i=1}^r \lceil { n_i \over 2 } \rceil then G contains $C_{n_1} + C_{n_2} + ... + C_{n_r} as a spanning subgraph. Here C_k denotes a cycle of length k. We prove this conjecture for n sufficiently large. 
Glenn Acree, Belmont University
"Cycles on Locally nconnected graphs"A graph is locally nconnected if the neighborhood of each vertex of the graph is nconnected. In 1979, Oberly and Sumuer made the following conjecture: If G is a connected, locally nconnected graph that does not contain an induced K(l,n+2), then G is Hamiltonian. Their paper proved the case for n=1, but little progress has been made since that time in terms of the general problem. The presentation will focus on the case for n=2, characteristics of locally 2connected K(1,4)free graphs. 
Brian Alpasch, Simon Fraser University "The Compost Heap of Graph Theory"One of the founding topics of graph theory was graph decompositions, in particular, decompositions of complete graphs into cycles of some fixed length. Throughout the development of graph theory, graph decompositions have maintained a central role. This talk will concentrate on surveying path and cycle decomposition results. There have been some very nice results posted over the years and there still are many intriguing unsolved problems involving path and cycle decompositions. 
Mark V Barovich, TBA
"The Cycle Space of a 3connected Hamiltonian Graph"Let G be a 3connected graph with minimum degree at least d and let Z(G) be the cycle space of G over the field GF(2). Adrian Bondy conjectured that if G has at least 2d vertices then every cycle in Z(G) can be written as the sum of an odd number of cycles, each having at least 2d1 edges. Removing the parity requirement produces the following slightly weaker conjecture: Conjecture 1: If G has at least 2d1 vertices then Z(G) has a basis consisting of cycles, each having at least 2d1 edges. Locke proved Conjecture 1 when G is not hamiltonian, exploiting relationships between longest cycles of G and their bridges. The case when G is hamiltonian requires a modified attack, by means of which Barovich and Locke have shown that if G is a counterexample to Conjecture 1 and v is the cardinality of the vertex set of G then G is hamiltonian, 8 < v < 4d7 and for every vertex x of G, Gx is 2connected or hamiltonian. 
Owen D. Byer, Northwestern College
"Maximizing the number of certain subgraphs in various classes of graphs"We present a precise upper bound on the number of paths of length two in a graph of fixed size and order, and completely describe the six classes of extremal graphs. We give a bound on the number of 4cliques in a 4partite graph. Finally, we give a new bound for number of paths of length three in a graph of fixed size, which trivially gives a bound on the number of 4cycles in a graph. Several conjectures are offered that would strengthen these results. 
Guantao Chen, Georgia State University
"Connectivities and Paths"Let $G$ be a graph and $u$ and $v$ be two arbitrary vertices of $G$. We will investigate the paths from $u$ to $v$ such that the resulting graphs of deleting of vertices of any of these paths still have some required connectivites. 
Jill Faudree, Emory University "On kOrdered Graphs"Ng and Schultz introduced the idea of cycle orderability. For a positive integer 4, a graph G is kordered if for every ordered sequence of k vertices, there is a cycle that encounters the vertices of the sequence in the given order. If the cycle is also a hamiltonian cycle, then G is said to be 1t kordered hamiltonian. We give minimum degree conditions, sum of degree conditions for nonadjacent vertices, and neighborhood union conditions that imply a graph is kordered hamiltonian. For example, we show that for a graph G on n vertices and any positive integer k, if the minimum degree of G is at least (rz + k  3)/2 for k odd or at least (n + k2)/2 for k even, then G is kordered hamiltonian. Ron Gould, Raplph Faudree, Michael Jacobson, Linda Lesniak 
Ralph Faudree, University of Memphis "Extremal Problems for Forbidden Pairs that Imply Hamiltonicity"Let C denote the claw K1,3, N the net (a graph obtained from a K3 by attaching a disjoint edge to each vertex of the K3), W the wounded (a graph obtained from a K3 by attaching an edge to one vertex and a disjoint path P3 to a second vertex), and Zi the graph consisting of a K3 with a path of length i attached to one vertex. For k a fixed positive integer and n a sufficiently large integer, the minimal number of edges and the smallest clique in a kconnected graph G of order n that is CYfree (does not contain an induced copy of C or of Y) will be determined for Y a connected subgraph of either P6, N. W. or Z3. It should be noted that the pairs of graphs CY are precisely those forbidden pairs that imply that any 2connected graph of order at least 10 is hamiltonian. These extremal numbers give one measure of the relative strengths of the forbidden subgraph conditions that imply a graph is hamiltonian. 
Ron Gould, Emory University
"On The Structure of 2Factors"A 2factor is a 2regular spanning subgraph of a graph, that is, the union of vertex dis joint cycles that spans the vertex set of the graph. The study of 2factors has long been a fundamentalarea of graph theory. The main concentration of this study has been on hamiltonian cycles, that is, single spanning cycles. However, significant strides have been made in the last few years on questions dealing with more general 2factors. The question of the exact structure (number of cycles and their length) will be considered as well as a variety of partial results in this direction. Extensions of several wellknown hamiltonian results will be presented along with some basic techniques used in these studies. 
Andras Gyarfas, University of Memphis
"On Colored Paths and Cycles" 
Ruth Haas, Smith College
"Trees that keep the walls from falling down"If we build a graph with pieces of wood as the edges and nails at the vertices, will it be a rigid object? We examine what conditions need to be true about the graph. This will turn out to depend on the tree structure of the graph. Several equivalent conditions will be discussed as well as generalizations. 
John Harris,Appalachian State University
"Long Paths: A Stroll Along Two Open Problems"In this talk we will examine two open problems regarding long paths, and we will discuss some of the progress that has been made toward solving them. The first problem relates to a conjecture by Gallai and work by Zamfirescu concerning the distribution of longest paths in connected graphs. The second problem stems from the work of Matthews and Sumner concerning clawfree graphs and hamiltonicity. 
Bill Jackson, Goldsmiths College
"Uniquely Hamiltonian Graphs"A graph is uniquely hamiltonian if it has exactly one hamilton cycle. I will describe some longstanding conjectures and some recent results on the structure of uniquely hamiltonian graphs 
Mike Jacobson, University of Louisville
"Twofactors with few components in clawfree graph"In a clawfree graph G, it has been shown that if the minimum degree is at least 4, then G contains a 2factor, i.e. as a spanning subgraph which is the union of cycles. In this talk, we will discuss the number of cycles that such a 2factor can have. In particular will show that when the minimum degree, say d, is sufficiently that there must be a 2factors containing at most n/d cycles which is essentially best possible. 
Tao Jiang, TBA
"Planar Hamiltonian Chordal Graphs are Cycle Extendable"A cycle $C$ in a graph $G$ is extendable if ther e exists a cycle $C'$ in $G$ such that $V(C')$ contains $V(C)$ and $V(C')=V(C )+1. A graph $G$ is cycle extendable if it contains at least one cycle and eve ry nonhamiltonian cycle is extendable. In this talk, we show that every plan ar hamiltonian chordal graph is cycle extendable. 
Hal Kierstead, TBA
"Combinatorial Card Tricks"Consider the following card trick performed by two partners Alice and Carol. While Carol is out of the room Alice gives Bob an Ncard deck D and asks Bob to choose any ncard hand H. Alice then orders H in a stack face down on a table. At this point Carol retu rns to the room, turns over the first n1 cards of the stack and then announces the last card without turning it over. We call this the (N, n)trick. It is a pleasant puzzle to solve the (52,5)trick. The (8 , 3) trick is somewhat more challenging. We show that for any n, the (n!+n1)trick can be performed by Alice and Carol in time and space polynomial in n. More formally, we show that for N=n!+n1, there exists a bijection e: C(D,n) > P(D,n1) with inverse d: P(D,n1) > C(D,n1) such that (1) for all hands H in C(D,n), the range of e(H) is contained in H and (2) e(H) and d(H) can be calculated in time and space polynomial in n, where C(D,n) denotes the collection of nsubsets of D, P(D,n1) denotes the collection of n1 permutations of D, and the range of a permutation (a_1, ..., a_n) is {a_1, ..., a_n}. 
Felix Lazebnik, University of Delaware
"Applications of Some Families of Algebraically Defined Graphs"Some families of algebraically defined graphs can be used to provide best known lower or upper bounds in some problems of extremal graph theory. In this talk I will discuss six such applications obtained in the last several years. All of them are based mainly on the construction discussed in the previous talk by A.J. Woldar. 
Jeno Lehel, University of Louisville
"Hamiltonian cycle, toughness, and chordal graphs"The removal of k vertices from a graph with a hamiltonian cycle cannot disconnect the graph into more than k connected components. The strengthening of this obvious connectivitylike property in terms of "toughness" of a graph may result in sufficient conditions for the existence of a hamiltonian cycle. Some results of this type will be discussed for particular families of graphs (among others, for chordal graphs). The general problem, known as Chvatal's comjecture, is still open. 
Stephen C. Locke, Florida Atlantic University
"Long Cycles and the Cycle Space of a Graph"Abstract: Adrian Bondy observed that any known and reasonable conditions which force a graph to have a long cycle, should force the graph to have lots of long cycles. I have worked mainly with conditions I would call Diractype.There are many ways to quantify this notion of lots of long cycles. One of my earlier papers shows that the graph must have cycles through any two prescribed vertices. Another shows that there is a long cycle by finding a collection of cycles and lower bound on the average length of the cycles in the collection.Yet another way to show that there are abundant long cycles is to show that they generate the cycle space. For our purposes, the cycle space is the vector space of even (eulerian) subgraphs, with symmetric difference as the addition operation and scalar multiplication by 0 or 1 is fairly obvious. It is also obvious that the cycles generate the cycle space. Conjecture (Bondy). Let G be a 3connected graph with minimum degree at least d and with at least 2d vertices. Then, every cycle of G is the sum of an odd number of cycles, each of length at least 2d1. I managed to prove (1985) this with the additonial hyypothesis that G be nonhamiltonian, and relaxing the requirement that an odd number of cycles be used. The "odd" condition will be rectified in a joint paper with Ms. Teng Cong, my M.S. student, along with a similar extension of Hartman's theorem. The "nonhamiltonian" condition will be weakened in a joint paper with my Ph.D. student, Mark Barovich. 
Lisa R. Markus, Furman University
"Vertex Disjoint Cycles in StarFree Graphs"Let $p$ denote the number of vertices in a graph and let $q$ denote the number of edges. Two cycles in a graph are {\it disjoint} if they have no common vertices. Pos\' a proved that any graph with $q \ge 3p5$ contains two disjoint cycles. Matthews and Sumner showed that if a graph is clawfree then only $p+6$ edges are needed to insure that the graph has two disjoint cycles. In this talk, we present generalizations of these results. In particular, in a $K_{1,r}$free graph, ($r \ge 4$), only $p + 2r  1$ edges are needed for there to be two disjoint cycles. Furthermore, a clawfree graph with $q \ge p + (3k1)(3k4)/2 + 1$ will contain $k$ disjoint cycles. (This is joint work with G. Chen, R.H. Schelp and H.S. Snevily) 
Enrique Moreno, TBA
"Simple hamiltonian graphs with minimum degree greater or equal than four have a second hamiltonian circuit"TBA 
Bruce Reed, TBA
"Mangoes and Blueberries"Erdos and Hajnal conjectured that for every $k$ there is an $f(k)$ such that if every subgraph $H$ of $G$ contains a stable set of size ${V(H) \over 2}k$ then there exists a set $X$ of at most $f(k)$ vertices such that $GX$ is bipartite. We sketch how this conjecture may be proved using an excluded minor structure theorem due to Robertson and Seymour. We also obtain that there is a $g(k)$ such that if $F$ has no half integral packing of $k$ odd cycles then it has an odd cycle cover of size at most $g(k)$. 
Russell S. Schwartz, M.I.T.
TBA 
HeinzJuergen Voss, Dresden, Germany
"Light subgraphs of polyhedral graphs"Fabrici and Jendrol' proved that each 3connected plane graph with a path of k vertices contains a path with k vertices such that each vertex has a degree at most 5k . Further they showed that each 3  connected plane graph with at least k vertices contains a connected subgraph on k vertices such that each vertex has a degree at most 4k+3 for each k at least 3 . Both bounds are sharp. Together with St. Jendrol' I generalized these results to polyhedral maps on compact 2manifolds and to 3connected graphs and 3  connected multigraphs embedded in compact 2  dimensional manifolds . In the talk I will report on our results on polyhedral maps on 2  dimensional manifolds. 
Peter Winkler, Bell Labs
"Cops, Robbers and Dismantlable Graphs"Fix a (finite, connected) graph G and consider the following game played by a "cop" and a "robber". First the cop selects a vertex of G as her starting position (the police station) and then the robber picks a vertex as his own starting position (the crime scene). Then the chase begins: the cop moves along an edge to a neighboring vertex, then the robber moves similarly, etc. The cop wins if she "captures" the robber, i.e. can contrive to occupy the same vertex at the same time; the robber wins if he can avoid capture forever. Each player sees what is happening, so the game is completely deterministic and one player or the other must have a winning strategy. On which graphs does the cop win? It turns out that these "dismantlable" graphs, first characterized in a 1984 paper with Richard Nowakowski, have just reappeared in work with Graham Brightwell motivated by problems from statistical mechanics. We'll give a tour of some of the curious properties of dismantlable graphs. 
AndrewWoldar, Villanova University
"General properties of algebraically defined graphs"In the last several years some algebraic constructions
of graphs
have appeared in the literature. Many of these
constructions were
motivated by problems from extremal graph theory, and
the graphs
obtained were primarily of interest in the context of
a particular
extremal problem. In the constructions cited below, it
soon becomes
evident that the obtained graphs have many interesting
properties
{\it beyond} those motivating their construction.
Moreover, these
properties remain present in graphs the construction
of which is
far more general. In our talk, we define these
generalized graphs
(bipartite and ordinary versions) and discuss their
properties,
which include {\it parallelotopy, embedded spectra,}
and $K_n$
and $K_{nn}${\it decomposability.} In the talk
which follows,
Professor Lazebnik will discuss a special case of our
constructions
which lead to graphs possessing many additional
interesting properties.

Allison Wolf, Emory University
"On kordered Hamiltonicity in Bipartite Graphs"For a positive integer k, a graph G is kordered if for every ordered sequence of k vertices there is a cycle that encounters the vertices of the sequence in the given order. If the cycle is hamiltonian, then G is said to be kordered hamiltonian. We give degree sum conditions for nonadjacent vertices that imply a bipartite graph is kordered hamiltonian. 
Xingxing Yu, Georgia Insitute of Technology
"Walks in Graphs"A kwalk in a graph is a closed walk which visits each vertex at least once and at most ktimes. Hence a 1walk is just a Hamilton cycle. We will discuss conditions for the existence of kwalks. 