Structural Invariants for Very Large Graphs

Definitions and mathematical statement

A numerical graph invariant is a numerical quantity assigned to a graph that is unchanged under graph isomorphism (equivalently, under relabeling of vertices). More formally, for a specified class of graphs $\mathcal G$ and a specified numerical value space $D$, an invariant is a function $I\colon\mathcal G\to D$ satisfying \[ G\cong H\ \Longrightarrow\ I(G)=I(H) \qquad(G,H\in\mathcal G). \] Here $\mathcal G$ and $D$ are placeholders: the supplied record specifies neither. The question also permits numerical data without explicitly requiring isomorphism invariance.

Source question. What kinds of numerical data or invariants should be extracted from very large graphs, such as protein-interaction graphs, to describe useful structural information?

This is an open-ended methodological question. The source does not specify the graph model, a size threshold for "very large," which structural features are relevant, or a criterion for usefulness. Protein-interaction graphs are given as an example, not as an exclusive domain. Consequently, the supplied information does not determine a quantified proposition, a particular invariant to construct, or a precise optimization or verification target. These qualifications remain unresolved.

Short English statement

The question asks which numerical summaries of very large graphs, including protein-interaction graphs, convey useful structural information. The intended graph class and meaning of usefulness are unspecified, so this remains a methodological research question requiring clarification before a precise theorem or construction task can be stated.

Sources

• Local registry: data/unsolvedmath/problems.json, permanent UnsolvedMath ID $30002274$, title "Structural Invariants for Very Large Graphs," source problem code catalogue entry; supplied collection: Oberwolfach Reports Open Problems.
• Supplied report citation: Graph Theory (2013), Oberwolfach Reports, pp. 67--128, DOI 10.4171/owr/2013/02. Source URL: https://doi.org/10.4171/owr/2013/02. The record describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions. No individual proposer is supplied.
• Supplied literature source, labeled "original Oberwolfach report": https://doi.org/10.4171/owr/2013/02.
• Literature assessment dated 2026-08-21: the supplied curation labels the problem open and describes it as an open-ended methodological question with no definite numerical invariant or proposition to verify. This is supplied dated curation, not an independently verified literature assessment; time-sensitive status and cited claims require independent verification.
• The supplied record labels the statement "exact" and reports that its mathematical content was checked against the official report, with notation, context, and question form normalized without changing the source-level claim. This verification claim is supplied provenance and has not been independently checked for this draft.