Dominating sets as marked centralizer covers in graph groups

Marked graph-group centralizers and an exact domination correspondence

Definitions and mathematical statement

Shared notation.

Standard number systems are $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$. Specialized notation and index ranges follow the cited source and the definitions below.

A graph problem is NP-hard when solving it permits solving every problem in NP through the specified efficient reductions. A graph group, commonly a right-angled Artin group, is generated by graph vertices with commutation relations on adjacent pairs. Encoding a graph problem in a group requires a computable construction and a correspondence between valid solutions.

Record scope and qualifications.

The catalogue title is retained as metadata. Named certificates, contracts, bounds or frameworks in that title are not asserted as results of the original source extract. Neither a graph problem nor a group construction is specified. No dominating-set or centralizer-cover reduction is inferred from the catalogue title. The supplied catalogue marks this record partially solved; its present research status was not independently checked. The source text below is rendered literally where necessary; damaged formulas and composite extracts are not silently repaired into a new mathematical claim.

Statement recorded in the supplied source.

Computational problems from graph groups

It is known that it is possible to establish correspondence between certain NP-hard graph problems and problems in group theory; we would like to expand our portfolio of such problems. [S2]

Source status.

The supplied catalogue labels this source record partially solved; that metadata was checked against the supplied snapshot on 2026-10-11. The label is preserved for provenance and is not an independent verification of present open status or mathematical correctness.

Short English statement

The source asks for more links between hard graph problems and computational group problems.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 20001324 (AIM-CRYPTOGRAPHY-0011). Catalogue curation and metadata: CC BY 4.0. The source extract is retained; definitions, English summaries and qualifications are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 AIM Workshop Problem Lists, source linked by catalogue record AIM-CRYPTOGRAPHY-0011. http://aimpl.org/postquantgroup/3/.

Verbatim supplied catalogue question

Computational problems from graph groups

It is known that it is possible to establish correspondence between certain NP-hard graph problems and problems in group theory; we would like to expand our portfolio of such problems.

Attempt and results

The source asks for additional graph/group correspondences, without selecting a graph problem. We examine the domination correspondence suggested by the supplied research summary, prove it completely, and test the attempted move to an unmarked group problem. This is a rederivation of supplied auxiliary material, not a claim of a new reduction or cryptographic hardness.

Commutation among marked generators.

For a finite simple graph $\Gamma=(V,E)$, define the right-angled Artin group \[ A_\Gamma=\langle v\in V:\ uv=vu\text{ when }\{u,v\}\in E\rangle. \] For distinct marked generators $u,v$, they commute if and only if they are adjacent. Adjacency gives the defining relation. If they are nonadjacent, send $u$ and $v$ to the two generators $a,b$ of the free group $F(a,b)$, and every other generator to the identity. Every prescribed commutation relation maps to a true relation, because none contains both $u,v$. Thus this defines a homomorphism. The commutator of $u,v$ maps to $aba^{-1}b^{-1}$, a nonempty reduced word in the free-group reduced-word model, so it is not the identity. This proves the converse. In particular, the intersection of the centralizer of $v$ with the marked vertex set is exactly its closed neighborhood $N[v]$, including $v$ itself.

The witness-preserving correspondence.

Define a marked centralizer cover to be a subset $D\subseteq V$ such that every marked generator belongs to the centralizer of at least one member of $D$. By the preceding equivalence, this says exactly that $V=\bigcup_{v\in D}N[v]$, which is the definition of a dominating set. The same subset is a witness in either problem, with the same cardinality; hence minimum cover size equals the domination number, including value zero for the empty graph. Constructing the marked presentation from the graph requires one commutator relator of length four per edge and a list of vertices, so the reduction has polynomial output size. A cover can be verified by checking graph adjacency, without solving a general group word problem. Any complexity classification imported from graph domination would require that external classification as an additional theorem; it is not reproved here.

Two exact composition checks.

For a disjoint union of graphs, no vertex in one component dominates a vertex in another. Restricting any dominating set to each component gives a dominating set there, and combining minimum component sets works. Thus domination, and our marked cover invariant, add across disjoint unions. For the join $\Gamma_1\vee\Gamma_2$ of two nonempty graphs, all cross edges are inserted. One vertex from each side dominates every vertex, so the value is at most two. A singleton dominates the join exactly when it dominates its own side; therefore the value is one if either side has a universal vertex, and two otherwise. These statements are about the marked presentations associated to those graphs; no general group decomposition algorithm follows.

Why the unmarked extension is false.

If a proposed group problem allowed arbitrary elements as centralizer centers, the identity would be a valid single center because $C_G(1)=G$. Then every nonempty finite set would have a one-center cover, regardless of its graph domination number. For example, an edgeless graph with $r\ge2$ vertices has marked cover number $r$, since each marked generator commutes with no other marked generator, but arbitrary centers make the value one. Thus marking and restricting the allowed centers are essential parts of the reduction; suppressing them does not create an intrinsic hard problem on a fixed abstract group.

Context, adversarial audit, and gap

The AIMPL section was unavailable; the workshop description and supplied snapshot were inspected. The audit checked nonadjacent generator retraction, closed rather than open neighborhoods, empty graphs, and the trivial identity center. The source's broader request for new useful correspondences and cryptographic applications is not settled by this known marked reformulation. No complexity or security lower bound beyond the explicit correspondence is claimed, and no computational experiment was performed.

Process and contributions

Mathematics and model-assisted adversarial self-audit: OpenAI gpt-6-astra, ultra reasoning, as dispatched for this research batch; exact serving revision not exposed. Codex (GPT-6; exact serving revision not exposed) materially assisted with orchestration and format review. No human mathematical authorship, mathematical edits, or independent human proof checking is asserted. Contribution prompt A was applied to the full definition and supplied source row, then prompt B was applied adversarially to the derived results. The item-specific audit above records the scope checks and rejected extrapolations. Local assembly and structural checks do not establish mathematical correctness. The source catalogue status is preserved in TOP_PROBLEM and is separate from this attempt status.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The proved material is a rederivation of known or auxiliary facts rather than a substantiated new advance on the original target. The proved marked domination correspondence does not establish novelty, unmarked or fixed-group hardness, or cryptographic security, and does not fulfill the open-ended portfolio agenda.

References

The complete original Sources subsection above is retained, including catalogue attribution and licence notices. The additional list records primary sources actually consulted for this attempt on 11 October 2026; uncited source links reproduced above were not all rechecked.

• Official AIM description, Post-quantum group-based cryptography; workshop provenance inspected. AIMPL pages failed retrieval, so exact graph-group agenda comes from the supplied snapshot. https://aimath.org/workshops/upcoming/postquantgroup/.

Final status

Unresolved in this attempt. The proved marked domination correspondence does not establish novelty, unmarked or fixed-group hardness, or cryptographic security, and does not fulfill the open-ended portfolio agenda.