DREI '98 Graph Theory & Combinatorial Optimization

"Spanning Cycles in Dense Graphs"

A conjecture of El-Zahar 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.

"Cycles on Locally n-connected graphs"

A graph is locally n-connected if the neighborhood of each vertex of the graph is n-connected. In 1979, Oberly and Sumuer made the following conjecture: If G is a connected, locally n-connected 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 2-connected 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.

"The Cycle Space of a 3-connected Hamiltonian Graph"

Let G be a 3-connected 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 2d-1 edges. Removing the parity requirement produces the following slightly weaker conjecture: Conjecture 1: If G has at least 2d-1 vertices then Z(G) has a basis consisting of cycles, each having at least 2d-1 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 < 4d-7 and for every vertex x of G, G-x is 2-connected or hamiltonian.

"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 4-cliques in a 4-partite 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 4-cycles in a graph. Several conjectures are offered that would strengthen these results.

"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 k-Ordered Graphs"

Ng and Schultz introduced the idea of cycle orderability. For a positive integer 4, a graph G is k-ordered 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 k-ordered hamiltonian. We give minimum degree conditions, sum of degree conditions for nonadjacent vertices, and neighborhood union conditions that imply a graph is k-ordered 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 + k-2)/2 for k even, then G is k-ordered 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 k-connected graph G of order n that is CY-free (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 2-connected 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.

"On The Structure of 2-Factors"

A 2-factor is a 2-regular 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 2-factors 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 2-factors. 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 well-known hamiltonian results will be presented along with some basic techniques used in these studies.

"On Colored Paths and Cycles"

"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.

"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 claw-free graphs and hamiltonicity.

"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

"Two-factors with few components in claw-free graph"

In a claw-free graph G, it has been shown that if the minimum degree is at least 4, then G contains a 2-factor, 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 2-factor can have. In particular will show that when the minimum degree, say d, is sufficiently that there must be a 2-factors containing at most n/d cycles which is essentially best possible.

"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.

"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 N-card deck D and asks Bob to choose any n-card 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 n-1 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!+n-1)-trick can be performed by Alice and Carol in time and space polynomial in n. More formally, we show that for N=n!+n-1, there exists a bijection e: C(D,n) -> P(D,n-1) with inverse d: P(D,n-1) -> C(D,n-1) 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 n-subsets of D, P(D,n-1) denotes the collection of n-1 permutations of D, and the range of a permutation (a_1, ..., a_n) is {a_1, ..., a_n}.

"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.

"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 connectivity-like 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.

"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 Dirac-type.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 3-connected 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 2d-1. I managed to prove (1985) this with the additonial hyypothesis that G be non-hamiltonian, 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 "non-hamiltonian" condition will be weakened in a joint paper with my Ph.D. student, Mark Barovich.

"Vertex Disjoint Cycles in Star-Free 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 3p-5$ contains two disjoint cycles. Matthews and Sumner showed that if a graph is claw-free 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 claw-free graph with $q \ge p + (3k-1)(3k-4)/2 + 1$ will contain $k$ disjoint cycles. (This is joint work with G. Chen, R.H. Schelp and H.S. Snevily)

"Simple hamiltonian graphs with minimum degree greater or equal than four have a second hamiltonian circuit"

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 $G-X$ 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)$.

TBA

"Light subgraphs of polyhedral graphs"

Fabrici and Jendrol' proved that each 3-connected 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 2-manifolds and to 3-connected 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.

"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.

"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.
Reference: F.~Lazebnik, V.A.~Ustimenko, and A.J.~Woldar, A new series of dense graphs of high girth, {\it Bull. AMS}{\bf 32}(1)(1995),73--79.

"On k-ordered Hamiltonicity in Bipartite Graphs"

For a positive integer k, a graph G is k-ordered 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 k-ordered hamiltonian. We give degree sum conditions for nonadjacent vertices that imply a bipartite graph is k-ordered hamiltonian.

"Walks in Graphs"

A k-walk in a graph is a closed walk which visits each vertex at least once and at most k-times. Hence a 1-walk is just a Hamilton cycle. We will discuss conditions for the existence of k-walks.