Set of tools and data to compute all known invariants for simple connected graphs
C++ Python TeX C Makefile
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
database @ 868dde8
report
src
templates
verification
.gitignore
.gitmodules
LICENSE
Makefile
README.md
options_simple_connected.json
requirements.txt
viewer.py

README.md

Encyclopedia of Finite Graphs

1408.3644 Integer sequence discovery from small graphs, also published in the August 2015 journal of Discrete Applied Mathematics.

zenodo.11304.png Encyclopedia of Finite Graphs code

zenodo.11280.png Simple Connected Graph Invariant database

This project has three major aims,

  1. To build an exhaustive reference database for graph invariants of a given class.
  2. To "mine" this database for sequences not present (or incomplete) in the OEIS.
  3. To use these sequences to suggest new mathematical relations between graph invariants.

Authors: Travis Hoppe and Anna Petrone

Requirements: The Encyclopedia calls upon many external libraries to generate the data. To fully repopulate the database, it requires numpy, networkx, graph-tool, sympy, pulp and, nauty. As an alternative, there is a standalone version of of the simple connected graph database for download.

Writeup: Integer sequence discovery from small graphs

In preparation for submission to either Journal of Integer Sequences, Discrete Applied Mathematics, or the Experimental Mathematics.

Integer Sequences Discovered

A catalog of all the sequences discovered and submitted to the OEIS.

Sequence Extensions: Sequences present in the OEIS, but extended.

Distinct Sequences: Sequences generated by distinct classes.

New Primary Sequences: Sequences generated by a single invariant conditions.

Secondary Sequences: Sequences generated by paired invariant conditions.

Relations: List of all the interesting (equality, subset and exclusive) relations between the sequences. Many of the relations are obviously true, some of these have been collected in a table.

Usage:

Visualization

Once the database is built, invariant conditions can be explored. For example, to display the only the three graphs that are simultaneously bipartite, integral and Eulerian with ten vertices:

python viewer.py 10 -i is_bipartite 1 -i is_integral 1 -i is_eulerian 1

Testing

First compile the invariant calculations, and run the unit test on the Petersen graph:

make compile
make test

Database

You can automatically download an updated copy of the database by cloning the database repository in the Encyclopedia directory:

git submodule add https://github.com/thoppe/Simple-connected-graph-invariant-database.git database

Note that we are unable to store the special invariants for larger graphs due to size constraints; these larger special invariants will have to be recomputed for n>6. We recommend rebuilding portions of the database as both a consistency check and a learning tool if you are considering adding additional invariants.

If the database has been updated, you can grab a new copy by running:

git submodule foreach git pull origin master

Calculated Invariants

Spectrum invariants

  • is_integral, (sympy)
  • is_rational_spectrum, is_distinct_spectrum

Note that older versions of the database incorrectly labeled is_distinct_spectrum as is_real_spectrum.

Subgraph invariants

Fractional invariants

Others

Trivial invariants

Future Invariants

Other Invariants (hard)

Other Invariants (trivial)