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

Encyclopedia of Finite Graphs code

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.

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.

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

• diameter, radius (networkx)
• is_eulerian (networkx)
• is_distance_regular (networkx)
• is_planar (graph_tool)
• is_bipartite (graph_tool)
• n_articulation_points (graph_tool)
• n_cycle_basis of which the n=0 case is_tree (networkx), circumference, girth
• degree_sequence, n_endpoints (trivial), is_k_regular, is_strongly_regular
• tutte_polynomial via the chromatic_polynomial leads to the chromatic_number
• automorphism_group_order (BLISS)
• k_vertex_connectivityk_edge_connectivity minimal number of nodes/edges that can be deleted to disconnect the graph.
• is_chordal (networkx)
• k_max_clique (networkx)
• is_hamiltonian

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

• is_subgraph_free_K3 of which the n=0 case is a triangle-free graph. (graph_tool)
• is_subgraph_free_K4, is_subgraph_free_K5 (graph_tool)
• is_subgraph_free_C4, ..., is_subgraph_free_C10 checks for cycles of length k (graph_tool)
• is_subgraph_free_bull, is_subgraph_free_bowtie, is_subgraph_free_diamond, is_subgraph_free_open_bowtie

Fractional invariants

• has_fractional_duality_gap_vertex_chromatic

Others

• maximal_independent_vertex_set also called the Independence number, n_independent_vertex_sets
• maximal_independent_edge_set, n_independent_edge_sets also called the Hosoya Index.

Trivial invariants

• n_edges
• n_vertex

• n_hamiltonian_cycles n_hamiltonian_paths
• is_perfect (SAGE)
• is_arc_transitive, is_vertex_transitive
• characteristic_polynomial
• spectrum
• is_cartesian_product (SAGE)
• is_well_covered

Other Invariants (hard)

• hajos_number
• crossing_number, toroidal_crossing_number
• sigma_polynomial, is_royle
• domination_number
• coarseness, thickness
• genus, skewness

Other Invariants (trivial)

• n_non_adjacent_vertex_pairs
• n_peripheral_points