back to table · edit · history · where entries came from · files · download
5969 bytes, as of the version from 2026-09-13 22:09. Recorded here, not run.
"""Characteristic polynomials of connected graphs -- numberdb.org/T237
phi(G, x) = det(xI - A(G)),
where A(G) is the adjacency matrix of the simple connected graph G. Graphs are
named by their graph6 string after canonical relabelling, matching the
chromatic and Tutte graph-polynomial tables.
Run it with SageMath:
$ sage -pip install numberdb # once
$ sage -python generate.py # check the table against this code
$ sage -python generate.py --publish # send it, with NUMBERDB_API_KEY set
The sign convention is det(xI - A), so the polynomial is monic. MathWorld's
worked examples use det(A - xI), which differs by (-1)^|V(G)|.
The generator computes every connected graph on at most seven vertices,
the same finite index used by T125 and T126. It also attaches the 35 common
graph names those tables use, and names connected cospectral mates in entry
comments.
Answers numberdb-data#67, for characteristic polynomials of natural small
matrices.
"""
import os
import sys
import numberdb.sage as numberdb
from sage.graphs.graph import Graph
from sage.graphs.graph_generators import graphs
from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
from sage.rings.integer_ring import ZZ
#: Largest graph in the table.
#:
#: Seven vertices gives 996 connected graphs, matching T125 and T126. The
#: measured longest entry is 51 characters, so the count is the constraint:
#: eight vertices would already be 11117 connected graphs.
MOST_VERTICES = 7
R = PolynomialRing(ZZ, "x")
x = R.gen()
#: The graph names already used by the chromatic and Tutte polynomial tables.
NAMED = {
"@": "complete graph $K_1$",
"A_": "complete graph $K_2$",
"BW": "path $P_3$",
"Bw": "complete graph $K_3$",
"CF": "star $K_{1,3}$",
"CL": "path $P_4$",
"C]": "cycle $C_4$",
"C^": "diamond graph",
"C~": "complete graph $K_4$",
"D?{": "star $K_{1,4}$",
"DBg": "path $P_5$",
"DBk": "bull graph",
"DB{": "dart graph",
"DFw": "complete bipartite graph $K_{2,3}$",
"DK{": "butterfly graph",
"DLo": "cycle $C_5$",
"DN{": "house X graph",
"D]{": "wheel $W_4$",
"Dbk": "house graph",
"D~{": "complete graph $K_5$",
"E?Bw": "star $K_{1,5}$",
"E?~o": "complete bipartite graph $K_{2,4}$",
"E@YO": "path $P_6$",
"EFz_": "complete bipartite graph $K_{3,3}$",
"EIe_": "cycle $C_6$",
"ELrw": "wheel $W_5$",
"E~~w": "complete graph $K_6$",
"F??Fw": "star $K_{1,6}$",
"F?B~o": "complete bipartite graph $K_{2,5}$",
"F?~v_": "complete bipartite graph $K_{3,4}$",
"F@HSO": "path $P_7$",
"FHQSO": "cycle $C_7$",
"FIefw": "wheel $W_6$",
"FjaHw": "Moser spindle",
"F~~~w": "complete graph $K_7$",
}
def _key_from_stdin():
if os.environ.get("NUMBERDB_KEY_FROM_STDIN") != "1":
return
token = sys.stdin.read().strip()
if "=" in token and token.split("=", 1)[0].isupper():
token = token.split("=", 1)[1].strip().strip("'\"")
if token:
os.environ["NUMBERDB_API_KEY"] = token
def connected_graphs(most_vertices=MOST_VERTICES):
"""Canonical connected graphs in the order the table displays them."""
for order in range(1, most_vertices + 1):
for graph in graphs.nauty_geng("%d -c" % order):
yield graph.canonical_label()
def characteristic_polynomial(graph):
"""The monic adjacency characteristic polynomial det(xI - A)."""
return R(graph.adjacency_matrix().charpoly("x"))
def graph_key(graph):
return graph.canonical_label().graph6_string()
def graph_from_key(key):
return Graph(str(key))
def _entry_ref(key):
# HREF{} is delimited by braces; graph6 keys containing a closing brace
# cannot be written there without changing the parser's grammar.
if "}" in key:
return "the graph with graph6 string `%s`" % key
return "HREF{#%s}" % key
def _joined_refs(keys):
refs = [_entry_ref(key) for key in keys]
if len(refs) == 1:
return refs[0]
return ", ".join(refs[:-1]) + " and " + refs[-1]
class CharacteristicPolynomials(numberdb.Generator):
table = os.environ.get("NUMBERDB_TABLE") or "T237"
parameters = ("g",)
type = "Z[]"
rigour = "exact"
#: Every polynomial, computed once, because comments name cospectral mates.
_values = None
def enumerate(self, most_vertices=MOST_VERTICES):
for graph in connected_graphs(most_vertices):
yield {"g": graph_key(graph)}
def all_values(self):
if self._values is None:
values = {}
for graph in connected_graphs():
values[graph_key(graph)] = characteristic_polynomial(graph)
self._values = values
return self._values
def value(self, params, digits):
key = str(params["g"])
values = self.all_values()
if key in values:
polynomial = values[key]
else:
polynomial = characteristic_polynomial(graph_from_key(key))
parts = []
if key in NAMED:
parts.append("This is the %s." % NAMED[key])
partners = [
other for other, other_polynomial in values.items()
if other != key and other_polynomial == polynomial
]
if partners:
parts.append("It is cospectral with %s." % _joined_refs(partners))
if parts:
return {"number": polynomial, "comment": " ".join(parts)}
return polynomial
if __name__ == "__main__":
_key_from_stdin()
generator = CharacteristicPolynomials()
if "--publish" in sys.argv or os.environ.get("NUMBERDB_PUBLISH") == "1":
print(generator.publish(
message="characteristic polynomials of connected graphs",
assisted_by=os.environ.get("NUMBERDB_ASSISTED_BY", "codex")))
else:
report = generator.verify(sample=None)
print(report)
sys.exit(0 if report.ok else 1)