Graph Encyclopedia (GES) v1.0

Subtitle: An OEIS for Graphs, Networks, Trees, DAGs, and Combinatorial Structures

---

Abstract

This document specifies the data schema, canonicalization protocol, serialization format, and query language for the Graph Encyclopedia Standard (GES).

GES provides a plaintext, peer-submittable registry of finite graphs and combinatorial structures.

Unlike existing graph databases, GES indexes graphs by their canonical topology, allowing structurally identical graphs to be automatically merged regardless of vertex labeling.

The primary objective is to create a universal infrastructure for graph theory analogous to the role played by the Online Encyclopedia of Integer Sequences for discrete mathematics.

---

1. Motivation

Currently:

• graphs are scattered across papers
• graph names are inconsistent
• isomorphic graphs appear multiple times
• graph properties are difficult to search

Example:

A graph can be represented as:

A-B
B-C
C-A

or

1-2
2-3
3-1

or

X-Y
Y-Z
Z-X

All describe the same topology.

GES solves this through canonical graph fingerprints.

---

2. Core Principles

A compliant implementation MUST satisfy:

Canonical Identity

Graphs are indexed by structure rather than labels.

Isomorphism Invariance

Two isomorphic graphs MUST resolve to the same identifier.

Plaintext Storage

Every entry must remain human-readable.

Property Richness

Every graph stores mathematical invariants.

Deterministic Serialization

Every graph has a unique canonical byte representation.

---

3. Entry Structure

Each graph receives a permanent ID:

G000001
G000002
G000003

---

Metadata Fields

%N

Name

%N Complete Graph K5

---

%V

Vertices

%V 5

---

%E

Edges

%E 10

---

%C

Comments

%C Smallest complete graph
%C Non planar

---

%P

Properties

%P planar=false
%P connected=true
%P bipartite=false

---

%R

References

%R Harary, Graph Theory

---

%K

Keywords

%K complete,dense,nonplanar

---

4. Graph Definition Language (Grapha)

GES introduces a DSL called:

Grapha

---

Example

GRAPH
VERTICES 5

EDGE 1 2
EDGE 1 3
EDGE 1 4
EDGE 1 5

EDGE 2 3
EDGE 2 4
EDGE 2 5

EDGE 3 4
EDGE 3 5

EDGE 4 5
END

---

5. Canonicalization Engine

The heart of GES.

Every submitted graph is transformed into:

Canonical Adjacency Form (CAF)

using graph isomorphism algorithms.

Recommended:

nauty
bliss
weisfeiler-lehman refinement

---

Example:

Both

1-2
2-3
3-1

and

A-B
B-C
C-A

produce:

CAF:
011
101
110

---

6. Fingerprint System

Every graph receives:

Graph Fingerprint (GF)

Generated from:

canonical adjacency matrix
+
degree sequence
+
spectral signature

---

Example:

GF:
sha256(CAF)

---

7. Mathematical Invariants

Every entry automatically computes:

Order

n = |V|

Size

m = |E|

Degree Sequence

(4,4,4,4,4)

Diameter

1

Radius

1

Chromatic Number

5

Clique Number

5

Eigenvalue Spectrum

4,-1,-1,-1,-1

Automorphism Group Size

120

---

8. Similarity Engine

Unlike identity matching:

Identity = exact isomorphism

Similarity allows discovery.

---

Graph Edit Distance

GED(A,B)

Minimum edge additions/removals needed.

---

Spectral Similarity

Compare eigenvalue vectors.

---

Structural Jaccard

J(V,E)

for local neighborhood overlap.

---

9. Derived Families

GES supports graph generators.

Example:

FAMILY CompleteGraph(n)

K1
K2
K3
K4
...

---

FAMILY CycleGraph(n)

C3
C4
C5
...

---

FAMILY Hypercube(n)

Q1
Q2
Q3
...

---

10. Query Language

GraphQL inspired syntax.

Example:

FIND
vertices > 50
connected = true
planar = false
diameter <= 3

---

Example:

FIND
chromatic_number = 4
clique_number = 3

---

11. Example Entry

====================================================
GRAPH ENCYCLOPEDIA ENTRY G000001
====================================================

%N Petersen Graph

%V 10

%E 15

%C Counterexample generator
%C Strongly regular graph

%P connected=true
%P planar=false
%P bipartite=false

%I chromatic=3
%I diameter=2
%I girth=5

%K cubic,strongly_regular,petersen

%G
GRAPH

EDGE 1 2
EDGE 2 3
EDGE 3 4
...
END

====================================================

---

12. Long-Term Vision

OEIS catalogs integer patterns.

GES would catalog topological patterns.

The real breakthrough is not storing graphs.

The breakthrough is:

Every graph ever published becomes addressable by a canonical identifier.

Then papers could cite:

GES:G003481

instead of redrawing the graph.