Characterization theorems for Zara graphs (Q1123911): Difference between revisions

A Zara graph is a finite graph satisfying the following two properties. i) There is a constant m s.t. every maximal clique has size m. ii) There is a constant e s.t. for every maximal clique M and every vertex x not in M, x is adjacent to e vertices in M. Zara graphs have a rich geometrical structure and it is conceivable that they can be completely classified. In this paper several classifications for subclasses of Zara graphs are given. In particular attention is focused on Zara graphs for which the geometric lattice on a maximal clique is the truncation of a Boolean lattice (these are completely classified if the rank is at least 6), and on Zara graphs for which the partial linear space on the maximal cliques is a near polygon. Finally the non-existence is shown of two Zara graphs which are related to completely regular two-graphs.