Source-linked AI summary
Generating cyclic pivot Gray codes for well-ordered $k$-degenerate graphs in constant amortized time
Lei Dong, Dennis Wong, Bowie Liu, Rui Bao, Lin Chen, Chan-Tong Lam, Sio-Kei Im
TL;DR
Multiple valid elimination orderings make labeled k-degenerate graph enumeration susceptible to overcounting, and pivot Gray codes for broader graph families remain an open question. The paper constructs a cyclic pivot Gray code for well-ordered k-degenerate graphs using a recursive approach based on pruned binary reflected Gray codes. Its generator runs in constant amortized time per graph and uses O(n^2) space.
Problem
A labeled k-degenerate graph can have multiple valid elimination orderings, complicating enumeration, while pivot Gray-code constructions for broader graph families remain open.
Source: §1 · pp. 4–5Method
A recursive algorithm builds the cyclic graph ordering using Gray codes for binary strings of weight at most k and the resulting pruned binary reflected Gray code.
Source: §2 · pp. 6, 7, 11Results
The GenWOD algorithm generates a cyclic pivot Gray code in constant amortized time per graph and uses O(n^2) space.
Source: §2 · p. 14Takeaways & Limitations
The generated ordering covers all well-ordered k-degenerate graphs, with consecutive graphs differing by one edge addition, removal, or pivot.
Source: §2 · p. 11The generation-time analysis excludes the time required to output each graph’s adjacency matrix.
Source: §2 · p. 14
Abstract
from arXiv · showhide
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.
1. Introduction
Enumerating labeled k-degenerate graphs is complicated by multiple valid elimination orderings, while Gray-code orderings for broader graph families remain an open construction challenge. The paper fixes labels as the ordering and introduces cyclic pivot Gray codes for well-ordered k-degenerate graphs.
1. Introduction
- A k-degenerate graph has an ordering in which each vertex has at most k earlier neighbors; such graphs include forests when k = 1 and outerplanar graphs when k = 2.The introduction also notes their connection to k-core decomposition and applications across several fields.Source: §1 · pp. 2–4
- Fixing vertex labels as the elimination ordering avoids the overcounting that can result when one graph has multiple valid elimination orderings.Well-ordered graphs require each vertex i to have at most k neighbors among vertices with smaller labels.Source: §1 · p. 4
- Pivot Gray codes had been constructed for several spanning-tree and directed-graph settings, but constructions for broader graph families remained open.The introduction also frames this question against Knuth’s open problem about a simple revolving-door listing of complete-graph spanning trees.Source: §1 · p. 5
- The paper constructs cyclic pivot Gray codes for well-ordered k-degenerate graphs by extending pivot operations to include a single edge insertion or deletion.A code is cyclic when its first and last graphs also differ by one pivot operation.Source: §1 · p. 6
- The paper proceeds from a recursive generation algorithm to an exact enumeration formula, then to ranking and unranking algorithms.The ranking and unranking algorithms determine a graph’s position in the generation order and recover a graph from a position.Source: §1 · p. 6
2. Pivot Gray Codes for Well-Ordered k-Degenerate Graphs
The section constructs a cyclic pivot Gray code for well-ordered k-degenerate graphs by recursively extending smaller graphs with neighbor sets in Gray code order. The resulting generator uses constant amortized time per graph and O(n^2) space.
2. Pivot Gray Codes for Well-Ordered k-Degenerate Graphs
- The neighbor sets follow the pruned BRGC, which lists strings of weight at most k and changes at most two bits between consecutive strings.Under the correspondence between strings and subsets, these changes mean adding, removing, or replacing one element; when weight reaches k, remaining bits are set to 0.Source: §2 · pp. 7, 10
- For each smaller base graph, GenWOD adds vertex n with a neighbor set of size at most k, alternating forward and reverse subset orders across base graphs.This alternating order preserves the transition between successive families of graphs.Source: §2 · pp. 10, 13
- The number of well-ordered k-degenerate graphs is one when n = 1 or k = 0, and is even when n ≥ 2 and k ≥ 1.The evenness follows by pairing graphs according to whether edge (1, 2) is present.Source: §2 · pp. 10–11
- The cyclic listing covers all well-ordered k-degenerate graphs, with consecutive graphs differing by one edge addition, removal, or pivot.The construction also ensures the last and first graphs satisfy this transition condition.Source: §2 · pp. 11, 13
- GenWOD generates the cyclic pivot Gray code in constant amortized time per graph using O(n^2) space.The analysis excludes the time to emit each graph; the algorithm maintains one n × n adjacency matrix.Source: §2 · p. 14
3. Enumeration
The section gives a closed-form enumeration formula for well-ordered k-degenerate graphs, offering a more explicit combinatorial representation than the recurrence used by Bauer et al..
3. Enumeration
- Theorem 7 gives the total number of well-ordered k-degenerate graphs on n labeled vertices in closed form.The section presents this as a more explicit combinatorial representation than Bauer et al.’s recurrence.Source: §3 · p. 16
- At each vertex v, the construction chooses a subset of earlier vertices with size at most k.These choices specify which edges join v to vertices labeled 1 through v − 1.Source: §3 · p. 16
- Because choices at different vertices are independent, their counts combine by the rule of product to count all graphs.Source: §3 · p. 16
- Theorem 7 also provides an alternative proof of Lemma 4.Source: §3 · p. 16
- The count is 1 when k = 0 and even when n ≥ 2 and k ≥ 1.Source: §3 · p. 16
4. Ranking and Unranking
This section develops ranking and unranking for well-ordered k-degenerate graphs using bounded-weight binary strings in pruned BRGC order, recursively decomposing graph indices into base-graph blocks and neighbor-set positions. Graph unranking reconstructs graphs on n vertices in O(n²) time and space.
4.1. Ranking and Unranking Binary Strings of Length n with Weight ≤k under the Pruned BRGC Order
- Reverse-order binary-string ranking and unranking follow from forward-order operations by converting rank r to |B_n,k| − r + 1.For reverse unranking, the corresponding forward-order index is |B_n,k| − r_rev + 1.Source: §4.1 · p. 17
4.1.1. Ranking for Binary Strings of Length n with Weight ≤k under the Pruned BRGC Order
- Binary-string ranking scans bits right to left, counts preceding blocks, and takes O(n) time after O(nk)-time preprocessing, using O(nk) space.The algorithm maintains the remaining one-budget and Gray-code direction while using precomputed block counts.Source: §4.1.1 · pp. 17–19
4.1.2. Unranking for Binary Strings of Length n with Weight ≤k under the Pruned BRGC Order
- Binary-string unranking selects each bit right to left by comparing the residual index with the first block size, taking O(n) time after O(nk) preprocessing and O(nk) space.When the target lies in the second block, the algorithm subtracts the first block's size before continuing.Source: §4.1.2 · pp. 19–21
4.2.1. Ranking for well-ordered k-degenerate Graphs
- Graph ranking recursively removes vertex n, combines the base-graph rank with the parity-selected neighbor-set rank, and runs in O(n^2) time and space.If i is the base-graph rank, j the neighbor-set rank, and M the number of extensions per base graph, the combined rank is (i − 1) · M + j.Source: §4.2.1 · pp. 22–23
4.2.2. Unranking for well-ordered k-degenerate Graphs
- Graph unranking splits an index into a base-graph block and neighbor-set offset, recursively reconstructs both, and returns the unique graph at that cyclic pivot Gray-code rank.It un-ranks the neighbor set in forward order for odd base-graph ranks and uses the reverse-order index for even ranks.Source: §4.2.2 · pp. 24–25
- GraphUnranking reconstructs well-ordered k-degenerate graphs on n vertices in O(n^2) time and uses O(n^2) space.Source: §4.2.2 · p. 26
- Its n recursion levels each cost O(m) at level m, and reconstruction uses one n × n adjacency matrix without creating graph copies.The quotient and remainder computation costs O(1), while unranking a binary string and reconstructing the edge sets cost O(m) per level.Source: §4.2.2 · p. 26
Appendix A. Python code to generate well-ordered k-degenerate graphs
Appendix A provides Python code for generating well-ordered k-degenerate graphs, with recursive traversal and a command-line wrapper.
Appendix A. Python code to generate well-ordered k-degenerate graphs
- The traversal uses recursive visit calls and tests whether i == -1 or weight == k.The code also recursively visits earlier indices in both forward and reverse modes.Source: Appendix A · p. 30
- GENWOD(n, k, visit=lambda A: None) is the generator entry point.The main routine calls GENWOD with the selected n and k.Source: Appendix A · pp. 30–31
- The command-line wrapper prints each generated graph as a matrix and then reports the total graph count.It invokes GENWOD after prompting for the input values.Source: Appendix A · p. 31
Appendix C. Python code for ranking well-ordered k-degenerate graphs
Appendix C supplies Python code that computes the rank of a well-ordered k-degenerate graph and displays the result.
Appendix C. Python code for ranking well-ordered k-degenerate graphs
- The implementation builds a count table and combines the recursive rank with the neighbor-set position to return the graph’s rank.The final rank is computed as (i-1) * m + j.Source: Appendix C · pp. 35–36
- The graph_ranking function extracts the last vertex’s neighbors and converts them into a binary string for ranking.The code calls the binary-string ranking routine and adjusts the rank for the reverse ordering when needed.Source: Appendix C · pp. 35–36
- The command-line interface accepts an adjacency matrix, calculates its rank, and prints the result.It also checks the row length and handles invalid input.Source: Appendix C · p. 36
Appendix D. Python code for unranking well-ordered k-degenerate graphs
Appendix D supplies Python code that reconstructs a well-ordered k-degenerate graph from its rank and displays the resulting matrix.
Appendix D. Python code for unranking well-ordered k-degenerate graphs
- The unranking function builds a count table and uses it to determine the bits of the neighbor set from the requested rank.The implementation compares and subtracts counts while traversing positions.Source: Appendix D · p. 37
- The fragments show null checks for C and G, an odd-index test using i % 2 != 0, and a call beginning unranking(C, n - 1, k, count(C, n - 1, k) - j +).Source: Appendix D · pp. 37–38
- The main function prints the matrix after formatting it: format_matrix processes each row, accumulates formatted rows, and returns them joined by newline separators as a single string.Source: Appendix D · p. 38