Нашли опечатку? Выделите ее мышкой и нажмите Ctrl+Enter

Название: On Construction and Identification of Graphs

Автор: Weisfeiler B.

Аннотация:

In this volume we give an exposition of some results and introduce some notions which were encountered during attempts to find a good method of graph identification. .
Sections of this volume are based mostly on unpublished papers of different people. I ask the reader who wishes to refer to papers constituting this volume to refer to them by the names given in the Table of Contents. Papers which are not followed by any name can be cited as my own.
The beginning of our work was the research described in [We3]. It was shown in this paper how to put into correspondence with any graph a nice combinatorial object. The authors were not conscious at the time of the writing [We3] that this combinatorial object this related 10 other problems. Later it turned out that the same object had been independently discovered and studied in detail by D. G. Higman [Hi3], [Hi5], [Hi6] and that such formations as strongly regular graphs, symmetric block designs, centralizer rings of permutatIons groups are special cases of this object (cf., Section F and L18). .
Although the properties of this object, called here a cellular algebra, were discussed by D. G. Higman [Hi3] , [Hi6] , we decided to state here some assertions about them. This done in the hope that it will help a reader to get acquainted with the notions and their use. .
At the same time the main stress is on the description of operations and constructions. Some assertions are proved to show how these constructions work. .
In an attempt to acquire a new understanding of the nature of our problems, much practical work was done, mostly with the help of computers. The most interesting outcome in this direction is probably the program which was designed to generate all strongly regular graphs with ≤32 vertices. This program constructed all strongly regular graphs with 25, 26, 28 vertices, but failed, for lack of time, to construct such graphs with 29 vertices. This work is described in Sections S-V. The strongly regular graphs with 25 and 26 vertices were intensively studied (cf., e. g., [Se5], [Sh4]).