Classifying strongly regular graphs using lexical ordering of adjacency matrices (Q757086): Difference between revisions

The concepts of lexical ordering and minimality of matrices are introduced. It is shown that every minimal matrix is lexically ordered, as a consequence of which it is shown that every matrix is isomorphic to at least one lexically ordered matrix. This property can be used while generating all matrices (up to isomorphism) satisfying a given condition, as it already reduces the number of matrices generated. But, as several lexically ordered matrices are isomorphic, also an algorithm to check isomorphism of two lexically ordered matrices is developed. As an immediate consequence of this, also an algorithm for the generation of the automorphism group of a lexically ordered matrix can be formulated. These results are then applied to graph theory where they can be used to formulate algorithms for the generation of adjacency matrices of strongly regular graphs.