Algebraic Combinatorics in Mathematical Chemistry. Methods and Algorithms. II. Program Implementation of the Weisfeiler-Leman Algorithm

Details Algebraic Combinatorics in Mathematical Chemistry. Methods and Algorithms. II. Program Implementation of the Weisfeiler-Leman Algorithm Algebraic Combinatorics in Mathematical Chemistry. Methods and Algorithms. II. Program Implementation of the Weisfeiler-Leman Algorithm

2010-02-09

arxiv.org/abs/1002.1921v1

Mathematics

Combinatorics

Arxiv version of a preprint published in 1997

Scientific paper

The stabilization algorithm of Weisfeiler and Leman has as an input any square matrix A of order n and returns the minimal cellular (coherent) algebra W(A) which includes A. In case when A=A(G) is the adjacency matrix of a graph G the algorithm examines all configurations in G having three vertices and, according to this information, partitions vertices and ordered pairs of vertices into equivalence classes. The resulting construction allows to associate to each graph G a matrix algebra W(G):= W(A(G))$ which is an invariant of the graph G. For many classes of graphs, in particular for most of the molecular graphs, the algebra W(G) coincides with the centralizer algebra of the automorphism group aut(G). In such a case the partition returned by the stabilization algorithm is equal to the partition into orbits of aut(G). We give algebraic and combinatorial descriptions of the Weisfeiler--Leman algorithm and present an efficient computer implementation of the algorithm written in C. The results obtained by testing the program on a considerable number of examples of graphs, in particular on some chemical molecular graphs, are also included.

Affiliated with

Also associated with

No associations

Rating

Algebraic Combinatorics in Mathematical Chemistry. Methods and Algorithms. II. Program Implementation of the Weisfeiler-Leman Algorithm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Algebraic Combinatorics in Mathematical Chemistry. Methods and Algorithms. II. Program Implementation of the Weisfeiler-Leman Algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algebraic Combinatorics in Mathematical Chemistry. Methods and Algorithms. II. Program Implementation of the Weisfeiler-Leman Algorithm will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-125133