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