ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

13. Combinatorics

1991 MS Classification: 5 Woldar, Andrew, Villanova University General properties of algebraically defined graphs In the last several years some algebraic constructions of graphs have appeared in the literature. Many of these constructions were motivated by problems from extremal graph theory, and the graphs obtained were primarily of interest in the context of a particular extremal problem. In the constructions cited below, it soon becomes evident that the obtained graphs have many interesting properties beyond those motivating their construction. Moreover, these properties remain present in graphs the construction of which is far more general. We define these generalized graphs (bipartite and ordinary versions) and discuss their properties, which include parallelotopy, embedded spectra, and K_{n}– and K_{nn}–decomposability.

Reference: F. Lazebnik, V. A. Ustimenko, and A. J. Woldar, A new series of dense graphs of high girth, Bull. AMS32(1)(1995),73–79.