Are Rotations Determined by Edge Labelings? 



A local rotation on a vertex in a graph is a cyclic permutation of its incident edges. A rotation on the graph is a collection of local rotations, one for each vertex. Rotations correspond to embeddings of the graph on orientable surfaces.

Suppose that the edges a graph G are labeled with the integers 1,,|E(G)|. This labeling induces a rotation on the edges incident with a vertex: place the edges in the cyclic order determined by increasing labels, with the edge with the largest label followed by the edge with the smallest. We call this the rotation induced by the labeling. The original form of this conjecture (for complete graphs only) was:

Possible Conjecture: Every rotation of G is induced by some edge-labeling.

However, this is easily disproved. The number of rotations for the complete graph K(n) is (n-2)!^n and the number of cyclic rotations on the edges is [n(n-1)]!; the former is larger than the latter for large n.

A second counterexample to the possible conjecture was given by Ulrich Brehm (as related by Vladimir Korzhik). Each face must have an edge i followed by an edge with edge j > i with at least one exception. The number of exceptions is at most |V|. Hence, every embedding of G induced by an edge-labeling of its edges has the number of faces |F| at most |V|.

Korzhik conjectures:

Conjecture: Every rotation of G inducing at most |V| faces is induced by an edge-labeling of its edges.

Conjecture: Every rotation of G corresponding to a maximal embedding of G is determined by an edge-labeling of its edges.

The first of these conjectures can perhaps be disproven by a counting argument similar to that above, examining the number of embeddings of a graph with fewer than |V| faces.

A second way to salvage the possible conjecture is to bound the degree of the graph. Dan Archdeacon (unpublished work) has shown that every embedding of a cubic graph is induced by an edge-labeling. He asks:

Question: If G is a graph of bounded degree d, then does there exist an N = N(d) such that any embedding of a graph of order exceeding N is induced by edge-labeling?

Dan Archdeacon notes that the question is unclear, even in the case d=4.

At the 2003 Ohio State Conference in honor of Neil Robertson, a participant pointed out that the general conjecture might be false even for the complete graph K(4). Dan Archdeacon calculated (but did not verify) that every embedding of K(4) is in fact induced by an edge-labeling.

There are no known applications of these conjectures, but they appear interesting.


Submitted by: Vladimir Korzhik, modified by Dan Archdeacon

Send comments to dan.archdeacon@uvm.edu

December 2003 (modified March 2004).