Generating cyclic pivot Gray codes for well-ordered $k$-degenerate graphs in constant amortized time

Abstract

A graph $G$ is $k$-degenerate if there exists an ordering $v_1,v_2,\dots ,v_n$ of its vertices such that each vertex $v_i$ has at most $k$ neighbors $v_j$ in $G$ with $j<i$. A well-ordered $k$-degenerate graph is a labeled graph on the vertex set $\{1,2,\dots ,n\}$ in which every vertex $i$ has at most $k$ neighbors among $1,2,\dots ,i-1$. We present the first simple algorithms that generate, rank, and unrank cyclic pivot Gray codes for well-ordered $k$-degenerate graphs, where consecutive graphs differ by the addition, removal, or pivoting of a single edge. Our algorithm generates each well-ordered $k$-degenerate graph in constant amortized time per graph, using $O(n^2)$ space, while ranking and unranking take $O(n^2)$ time and $O(n^2)$ space.

arXiv comment38 pages, 4 figures