back to table · edit · history · where entries came from · files · download
5021 bytes, as of the version from 2026-10-27 11:38 (current). Recorded here, not run.
"""Graph energies of connected graphs -- numberdb.org/T546.
Run with SageMath and the numberdb package:
sage -pip install numberdb
sage -python generate.py # verify all stored entries
sage -python generate.py --fill # fill this draft with NUMBERDB_API_KEY
The default census is all 142 connected simple graphs on 2 through 6 vertices.
Canonical identifiers use Sage's algorithm='sage'; the build used Sage 10.9.
No input graph or polynomial data is required. See argument-selection.md for
selection policy and checks.py for an independent matrix diagonalization.
Exact irreducible factors whose roots have one sign contribute their signed
integer trace. Mixed-sign factors are evaluated by certified real algebraic
root isolation followed by interval arithmetic, without forming a compositum.
The initial guard is 80 bits; width is checked and precision doubles if needed.
Only a proven integer is returned exactly. No rounding-based integer detection
is used. Filling entries never publishes or offers the draft.
"""
import os
import sys
from functools import lru_cache
import numberdb.sage as numberdb
from sage.graphs.graph import Graph
from sage.graphs.graph_generators import graphs
from sage.rings.integer_ring import ZZ
from sage.rings.qqbar import AA
from sage.rings.real_mpfi import RealIntervalField
WORKING_GUARD = 80
def graph_from_key(key):
graph = Graph(key, format='graph6')
if graph.order() < 2 or not graph.is_connected():
raise ValueError('Expected a connected simple graph with at least two vertices')
return graph
@lru_cache(maxsize=None)
def spectral_factors(key):
polynomial = graph_from_key(key).adjacency_matrix().charpoly()
answer = []
for factor, multiplicity in polynomial.factor():
roots = factor.roots(ring=AA)
assert sum(int(k) for _, k in roots) == factor.degree()
assert all(k == 1 for _, k in roots)
signs = {int(root.sign()) for root, _ in roots}
if signs <= {0, 1}:
exact = -factor[factor.degree()-1]
elif signs <= {-1, 0}:
exact = factor[factor.degree()-1]
else:
exact = None
answer.append((int(multiplicity), tuple(r for r, _ in roots), exact))
return tuple(answer)
def energy(key, digits=100):
factors = spectral_factors(key)
exact_part = sum((ZZ(m) * c for m, _, c in factors if c is not None), ZZ(0))
mixed = [(m, roots) for m, roots, c in factors if c is None]
if not mixed:
return exact_part
bits = numberdb.bits(digits, losing=WORKING_GUARD)
while True:
field = RealIntervalField(bits)
result = field(exact_part)
for multiplicity, roots in mixed:
for root in roots:
result += multiplicity * abs(field(root))
lower, upper = result.endpoints()
width = upper.exact_rational() - lower.exact_rational()
if lower > 0 and width > 0 and width < ZZ(10)**(-ZZ(digits+10)):
return result
bits *= 2
if bits > 16384:
raise ArithmeticError('Could not obtain a finite narrow enclosure')
def graph_comment(graph):
n = graph.order()
degrees = graph.degree()
if graph.size() == n * (n-1) // 2:
return 'This is the complete graph $K_{%d}$.' % n
if graph.is_bipartite():
left, right = graph.bipartite_sets()
a, b = sorted((len(left), len(right)))
if graph.size() == a*b:
return 'This is the complete bipartite graph $K_{%d,%d}$.' % (a,b)
if graph.size() == n-1 and max(degrees) == 2:
return 'This is the path $P_{%d}$.' % n
if all(d == 2 for d in degrees):
return 'This is the cycle $C_{%d}$.' % n
return None
class GraphEnergies(numberdb.Generator):
table = 'T546'
parameters = ('g',)
type = 'R'
digits = 100
rigour = 'proven'
files = ('generate.py', 'checks.py', 'argument-selection.md')
def enumerate(self, max_vertices=6):
for n in range(2, max_vertices+1):
keys = sorted(graph.canonical_label(algorithm='sage').graph6_string()
for graph in graphs.nauty_geng('%d -c' % n))
assert len(keys) == len(set(keys))
for key in keys:
yield {'g': key}
def value(self, params, digits):
key = params['g']
result = {'number': energy(key, digits)}
comment = graph_comment(graph_from_key(key))
if comment:
result['comment'] = comment
return result
if __name__ == '__main__':
if os.environ.get('NUMBERDB_KEY_FROM_STDIN') == '1':
numberdb.configure(api_key=sys.stdin.read().strip())
generator = GraphEnergies()
if '--fill' in sys.argv or os.environ.get('NUMBERDB_PUBLISH') == '1':
print(generator.publish(message='Fill complete order-two-through-six graph-energy census'))
else:
report = generator.verify(sample=None)
print(report)
sys.exit(0 if report.ok else 1)