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 (Q1241450)

The book investigates algebraic structures called cellular algebras by the author. This structure arose in a general graph canonization algorithm and it has a wide range of applications. The centralizer ring of a permutation group, and the algebra generated by the adjacency matrix of a strongly regular graph are particular classes of it. The author points out that cellular algebras are the same as the adjacency algebras of \textit{D. G. Higman}'s coherent configurations [Geom. Dedicata 4, 1--32 (1975; Zbl 0333.05010)]. Complete graphs with coloured and directed edges are considered, and distinct non-commuting variables are associated with each color. The adjacency matrix has these variables for its entries. With any such matrix \(A=(a_{ij})\) another matrix \(B=(b_{ij})\) of this kind (but with a possibly larger number of colours) is associated by the rule that \(b_{ij}=b_{kl}\) if and only if \(a_{ij}=a_{kl}\), \(a_{ji}=a_{lk}\) and these relations hold for \(A^2\), too. \(A\) is stationary, if \(B\) has the same number of colours as \(A\) (i.e., the colours of \(A\) do not split). Geometrically this means that (i) the colour of the edge \((a,b)\) is determined by the colour of \((b,a)\); (ii) given the colours \(x\) and \(y\) and the points \(a,b\), the number of \(a\to c\to b\) paths of length 2 having colours \(x\) and \(y\), depends on the colour of \((a,b)\) only. The matrices obtained by substituting elements of a ring for the variables in a stationary matrix form a cellular algebra. The stabilization procedure and refinements of of it are applied to obtain graph canonization algorithms. The structure of cellular algebras is studied in detail. Concepts originating from permutation groups are introduced. The last chapters of the main part of the book are concerned with practical algorithms of graph canonization and of constructing strongly regular graphs. All strongly regular graphs with \(10\leq n\leq 28\) vertices are determined. The obtained tables are analyzed. The appendix contains further applications of the theory. Also, some problems are mentioned. The canonization algorithm is conjectured to have \(n^{C\log n}\) running time. There are no theoretical estimates of the running time in the book. Though the book represents an algebraic approach, the geometrical meaning of the concepts and formulas is always emphasized. The bibliography contains about 130 items. The book contains numerous unpublished results of some colleagues of the author. The procedure leading to a stationary graph and a great deal of the results on cellular algebras were invented by A. A. Lehman (A. A. Leman). The practical canonization algorithm is due to V. Arlazarov, I. Faragev, A. Uskov, I. Zuev. The results on strongly regular graphs were obtained by M. Rosenfeld. Table of Contents: Introduction. Conventions, assumptions, notations. A. Some remarks about the problem of graph identification. B. Motivation (after A. Lehman). C. A construction of a stationary graph (after A. Lehman). D. Properties of cells (after A. Lehman). E. Properties of cellular algebras of rank greater than one. F. Cellular algebras arising in the theory of permutation groups. G. Some classes of cellular algebras. H. Imprimitive cells and construction of factor-cells (after A. Lehman). I. Construction of the quotient in the case of cellular algebras of rank greater than one (after A. Lehman, B. Weisfeiler). J. On the structure of correct stationary graphs and cells having more than one normal subcell. K. Properties of primitive cells (after A. Lehman). L. Algebraic properties of cellular algebras. M. Some modifications of stabilization. N. Kernels and stability with respect to kernels. O. Deep stabilization. P. Examples of results using stability of depth 1. Q. Some definitions and explanations about exhaustive search (after G. M. Adelson-Velsky, V. Arlazarov, B. Weisfeiler). R. An algorithm of graph canonization. S. A practical algorithm of graph canonization (after V. Arlazarov, I. Faragev, A. Uskov, I. Zuev). T. An algorithm of construction of strongly regular graphs (after M. Rosenfeld). U. Tables of strongly regular graphs with \(n\) vertices \(10\leq n\leq 28\) (after M. Rosenfeld). V. Some properties of 25- and 26-families (after M. Rosenfeld). Appendix. AA. A graphical regular representation of \(\mathrm{Sym}(n)\) (after A. Lehman). AB. A graphical regular representation of \(\mathrm{SL}_n(\mathbb F_q)\). AC. One more example of a cell with one generator. AD. Deep constants. AE. Algebraic invariants of finite graphs. AG. Conjectures. Bibliography. Distribution of the bibliography per topics. Index of notations. Subject index