Graph Theory Roadmap

This page aims at documenting the progress of the Graph Theory component of Sage.

Comparison with other graph theory software

• This page aims at comparing the features implemented in Mathematica that are missing in Sage.

• The features from Maple that are missing in Sage are tracked here.

Missing features

Graph constructions

The following (families of) graphs are still to be introduced into Sage

•  Folkman graph.
• Sierpinski graph

Graph predicates

• Testing if a graph is distance-transitive. See  http://mathworld.wolfram.com/Distance-TransitiveGraph.html
• Testing if a graph is distance-regular. See  http://mathworld.wolfram.com/Distance-RegularGraph.html

Graph operations

The following graph operations are still missing.

• The  join of a graph.

Performance improvements

Following is a list of tasks that can be done more efficiently than in the current implementation.

• Computing the list of neighbouring vertices efficiently. See ticket #13730.

Misc

• Add a function to return the distance matrix of a graph. See ticket #14056