99-28: On Parallel Edges in Cycles

DIMACS TR: 99-28

On Parallel Edges in Cycles

Authors: E. Boros and V. Gurvich

ABSTRACT
Let $n\leq N$ be positive integers. We consider the problem of finding an $n$-cycle with no parallel edges in a perfect $N$-gon in the Euclidian plane. We prove that there exist no such $n$-cycle if and only if $N=n$ and even. And we show by construction that for every other pair $(N,n)$, $N \geq n \geq 3$, such an $n$-cycle exists.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-28.ps.gz

DIMACS Home Page