Steve Hedetniemi

Department of Computer Science

Clemson University

Clemson, SC 29634-1906

- CYCLES IN N-CONNECTED GRAPHS [Hedetniemi, 1993]
- INSTANCE: An n-connected graph G = (V,E), a set S of n>2 vertices.
- QUESTION: Can you construct in polynomial time a cycle containing all of the vertices in S?

It is known that such a cycle always exists. For n=2 such a cycle can be constructed in polynomial time.

- GRID TSP [Hedetniemi, 1993]
- INSTANCE: An edge-weighted, complete M x N grid graph G = (V,E), and a positive integer K.
- QUESTION: Does there exist a Hamiltonian cycle in G of weight <= K?

- DISJOINT CYCLES [Posa, 1963]
- INSTANCE: A graph G = (V,E) with n vertices and >= 3n-5 edges.
- QUESTION: Does G contain two disjoint cycles?

The answer to this question is always, yes, due to a theorem of Posa. My question is: can you find two disjoint cycles in such a graph in polynomial time? [L. Posa, On the circuits of finite graphs, Magyar Tud. Akad. Mat. Kutato Int. Kozl., 8 (1963), 355-361]

- HAMILTONIAN CYCLE IN RANDOM CUBIC GRAPHS [Wormald and Robinson, 19XX]
- INSTANCE: A random, cubic graph G = (V,E).
- QUESTION: Does G contain a Hamiltonian cycle?

Robinson and Wormald have proved that almost all random, cubic graphs are Hamiltonian. My question is: given a random, cubic graph can you find such a Hamiltonian cycle in polynomial time? Bollobas, when asked about the difficulty of computing a typical optimization parameter of a random graph, speculated that most, if not all, NP-complete problems have linear solutions when restricted to random graphs. Thus, using the Bollobas 'thesis', it should be easy to find a Hamiltonian cycle in a random, cubic graph.

- HAMILTON CYCLE IN CAYLEY GRAPH
- INSTANCE: A Cayley graph G = (V,E).
- QUESTION: Does G contain a Hamiltonian cycle?

A Cayley graph G(X) is obtained from an arbitrary group G and a finite set X of generators for G. The vertices of G(X) correspond 1-1 with the vertices of G, and two vertices u and v are adjacent in G(X) if and only if the equation ux = v holds for some generator x in X. It has long been conjectured that every Cayley graph is Hamiltonian.

- HAMILTONIAN CYCLE IN 4-REGULAR PRISM GRAPHS [Rosenfeld, 198X]
- INSTANCE: A 4-regular prism graph G = (V,E).
- QUESTION: Does G contain a Hamiltonian cycle?

Let G be an arbitrary cubic graph and let G' be a copy of G. The prism graph on G is formed by adding edges between each vertex v in G and its isomorphic copy v' in G'. According to Rosenfeld it is not known whether every such 4-regular prism graph is Hamiltonian.

- RANDOM HAMILTONIAN TREE WALK [Wilf, 198X]
- INSTANCE: A rooted tree T = (V,E,r) with |V| = n vertices.
- QUESTION: What is the expected length of a random Hamiltonian walk in T, starting at the root r?

The object here is to start a random walk at vertex r and keep walking until all vertices have been visited at least once (it isn't necessary to return to the starting vertex). Having arrived at a given vertex v, the next vertex visited is chosen among its neighbors with equal probability. Wilf says that the expected length of such a walk is no greater than O(n

^{3}). The expected length is known for paths and cycles and a few other classes of graphs. - EXCHANGE MINIMUM TSP [Tovey, 198X]
- INSTANCE: An edge-weighted complete graph G = (V,E),
- QUESTION: How difficult is it to find a Hamiltonian circuit whose weight cannot be lowered by an exchange of a pair of edges?

- VERTEX TRANSITIVE HAMILTONIAN PATH [Lovasz, 198X]
- INSTANCE: A vertex transitive graph G = (V,E).
- QUESTION: Does G have a Hamiltonian path?

Actually, Lovasz asks, does every vertex transitive graph have a Hamiltonian path?

- DOUBLE CYCLE [Johnson, 19XX]
- INSTANCE: A graph G = (V,E) which is bridgeless.
- QUESTION: Does there exist a family C of cycles of G (not necessarily distinct) such that each edge of G appears in exactly two cycles of C?

- CHORD REALIZABLE GRAPH [Rosenfeld, 198X]
- INSTANCE: A set of n positive integers {l1, l2, ... , ln}, such that each li >= 3.
- QUESTION: Does there exist a Hamiltonian cubic graph G on 2n vertices whose short chord lengths are {l1,l2,...,ln}?

Let v

_{1}, v_{2}, ... , v_{2n}be the vertices, in order, of a cycle C. If we add an arbitrary chord to C, say between vertices v_{i}and v_{j}, then the short chord length of this chord is the minimum distance between v_{i}and v_{j}in C. - CYCLE REALIZABLE GRAPH [Jacobson, 1993]
- INSTANCE: An n-tuple A[1..n] of 0's and 1's.
- QUESTION: Does there exist a graph G = (V,E) with n vertices such that G has a cycle of length i, 3 <= i <= n if and only if A(i) = 1 {we assume that A[1] = A[2] = 0}.