The TuttePolynomial command uses a new algorithm that is faster and consumes less memory.

For example, computation of the Tutte polynomial of the 12 vertex complete graph (CompleteGraph(12)) now requires 1/3 the memory, and completes in 1/3 the time.

For the 9,3 generalized Petersen graph (PetersenGraph(9,3)) the memory usage has dropped to 1/6, and the time to 1/8 of the time needed in Maple 16.

These improvements propagate to the commands ChromaticPolynomial, FlowPolynomial, AcyclicPolynomial and RankPolynomial as well.

The IsIsomorphic command now utilizes a new algorithm that scales better to larger problems. As an example, two isomorphic soccer ball graphs (SpecialGraphs[SoccerBallGraph]) with 60 vertices and 90 edges can be tested for isomorphism in less than one second in Maple 17, while in Maple 16 and earlier, this same computation did not complete in under 10 minutes.

The new LaplacianMatrix command can be used to compute the Laplacian matrix representation of a graph:

The new ReliabilityPolynomial command can be used to compute the reliability polynomial of a graph:

GraphTheory, GraphTheory[LaplacianMatrix], GraphTheory[ReliabiltyPolynomial]