On Construction and Identification of Graphs
- PDF / 8,426,688 Bytes
- 251 Pages / 461 x 684 pts Page_size
- 54 Downloads / 203 Views
558 I
Boris Weisfeiler
On Construction and Identification of Graphs
Springer-Verlag Berlin.Heidelberg • New York 19 7 6
Boris Weisfeiler Department of Mathematics Pennsylvania State University University Park, PA 16802
Library of Congress Cataloging in Publication Data
Main entry under title: On construction and i~entification of graphs~ (Lecture notes in mathematics ~ 558) Bibliography: p. Includes indexes. 1. Graph theory--Addresses~ essays~ lectures° I. Weisfeiler, Boris, 1941IIo Series : Lecture notes in mathematics (Berlin) ~ 558° Q~3.L28 noo 5 58 [QA166] 510'.8s [511'.5] 76-54232
AMS Subject Classifications (1970): 05CXX, 05 B30, 05-04 ISBN 3-540-08051-1 ISBN 0-387-08051-1
Springer-Verlag Berlin • Heidelberg • NewYork Springer-Verlag New York" Heidelberg • Berlin
This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically those of translation, reprinting, re-use of illustrations, broadcasting, reproduction by photocopying machine or similar means, and storage in data banks. Under § 54 of the German Copyright Law where copies are made for other than private use, a fee is payable to the publisher, the amount of the fee to be determined by agreement with the publisher. © by Springer-Verlag Berlin • Heidelberg 1976 Printed in Germany Printing and binding: Beltz Offsetdruck, Hemsbach/Bergstr.
B ~enHx
npHpo~m
B nen2x
pacce~TB
06ys~aHHH HeyYeHB~
T~My
Eep~
E
TynO
KapT~Hy
uHp0s~aMH~
CMOTpHM? ( A.
qTO
H S.
-- ~a!
K qeMy...
CTpyra~K~e
... en v~rit~ le chemin importe peu, la volont~ d'arriver suffit a tout.
( A. Camus )
)
Acknowledgement I am greatly indebted to Professor J. J. Seidel.
His interest in the
problems discussed in this volume encouraged me and his criticism, both mathematical and linguistical, helped to make the manuscript better.
I am also grateful to
Professor D. G. Corneil~ who sent me many preprints of his work~ and to J. Hager for linguistical corrections.
It is a pleasure to thank here C. D. Underwood~ the
Administrative Officer of the School of Mathematics,
I.A.S.,
for her patience and
help during my stay at the Institute~ and the Secretaries~ I. C. Abagnale~ A. W. Becker, E. T. Laurent~ and M° M. Murray for their excellent typing.
I am
also grateful to the Institute for Advanced Study for support during my stay there.
B. Weisfeiler
TABLE OF CONTENTS Introduction
VII
Conventions~ assumptions~ notations
XI
A. B. C. D. E. F. G. H. I.
1 5 13 23 29 38 41 48
J. K. L. M. N. O. P. Q. R. S. T. U. V.
Some remarks about the problem of graph identification Motivation (after A. Lehman) A construction of a stationary graph (after A. Lehman) Properties of cells (after A. Lehman) Properties of cellular algebras of rank greater than one Cellular algebras arising in the theory of permutation groups Some classes of cellular algebras Imprimitive cells and construction of factor-cells (after A. Lehman) Construction of the quotient in the case of cellular algebras of rank greater than one (after A. Le
Data Loading...
