Classifying strongly regular graphs using lexical ordering of adjacency matrices

DOI10.1016/0898-1221(91)90076-GMaRDI QIDQ757086zbMATH OpenOpenAlexFDO

Authors Kris Coolsaet, V. Fack

Publication date 1991

Published in Computers & Mathematics with Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0898-1221(91)90076-g

zbMATH Keywords

classification algorithmlexical orderingstrongly regular graphs

Mathematics Subject Classification ID

Axiomatics of classical set theory and its fragments (03E30) Graph theory (including graph drawing) in computer science (68R10)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 4193150
• Doubly Lexical Orderings of Matrices
• Graphs represented by extended diagonal matrices
• Adjacency Matrices
• Extremal matrices for the Bruhat-graph order

Cites work

• An algorithm for the classification of strongly regular graphs by means of lexically ordered adjacency matrices
• scientific article; zbMATH DE number 3884175 (Why is no real title available?)
• scientific article; zbMATH DE number 3664952 (Why is no real title available?)
• scientific article; zbMATH DE number 3670480 (Why is no real title available?)
• On construction and identification of graphs. With contributions by A. Lehman, G. M. Adelson-Velsky, V. Arlazarov, I. Faragev, A. Uskov, I. Zuev, M. Rosenfeld and B. Weisfeiler
• Strongly regular graphs
• Strongly regular graphs, partial geometries and partially balanced designs

Cited in

(1)

• scientific article; zbMATH DE number 4193150 (Why is no real title available?)

This page was built for publication: Classifying strongly regular graphs using lexical ordering of adjacency matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q757086)