# DREI '98 Graph Theory & Combinatorial Optimization

## July 20 - 24, 1998

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

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

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

Lisa R. Markus, Furman University

#### "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)

Enrique Moreno, TBA

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

 Russell S. Schwartz, M.I.T. TBA

Heinz-Juergen Voss, Dresden, Germany

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

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

Allison Wolf, Emory University

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

Xingxing Yu, Georgia Insitute of Technology

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