Constructive characterization of dumpy graphs

Definitions and mathematical statement

Recorded problem. Find a constructive characterization of $k$-dumpy graphs.

The defining term "$k$-dumpy" is not explained anywhere in the supplied record. Neither the permitted values of $k$ nor the graph category (for example, simple graphs versus multigraphs) is specified. It would be mathematically unsafe to infer a definition merely from the summary's connection with connectivity augmentation and rigidity theory.

In the usual graph-construction sense, the requested result would specify initial graphs and explicit graph operations, and prove that the graphs obtainable by those operations are exactly the $k$-dumpy graphs. If $\mathcal D_k$ denotes the as yet undefined source class and $\mathcal C_k$ the class generated by a proposed construction, the required soundness and completeness would be \[ \mathcal C_k=\mathcal D_k. \] This equality only expresses the requested kind of characterization; it is not a substitute definition of dumpiness. The actual predicate defining $\mathcal D_k$ must be recovered before a source-specific membership or construction theorem can be formulated. The record also does not specify whether "constructive" requires finitely many moves, a reduction sequence, effective recognition, or a particular running time, so no algorithmic complexity promise is added.

The supplied research summary says the Egres list classes this characterization as open and no verified construction was found. The background explicitly warns that the archived wiki is not a current resolution authority. No present-day openness or nonexistence of a characterization is independently asserted.

Short English statement

Give explicit starting graphs and construction rules that generate exactly the $k$-dumpy graphs. The supplied record omits the definition of $k$-dumpy and the allowed parameter and graph ranges, so the precise target class cannot be recovered from this excerpt.

Sources

• Local UnsolvedMath registry, permanent ID 3000020, source code catalogue entry, "Constructive characterization of dumpy graphs"; supplied status open, classification OPEN-TRIAGE, updated 2026-08-06. No proposer is supplied.
• Egres Open, List of open problems, indexed page "Constructive characterization of dumpy graphs"; supplied index URL https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems. The record reports HTML extraction and access on 2026-07-29. The index classified the page as open, but the record says the archived wiki is not a current resolution authority.
• Rights note from the record: NEEDS_REVIEW; public wiki access was verified, but no redistribution license was displayed in the archived footer. No direct problem-page URL or primary paper is supplied.