Graphs With The 3-B.C. Adjacency Property Constructed from Affine Planes

Abstract

A graph $G$ is 3-e.c. if for each distinct triple $S$ of vertices, and each subset $T$ of $S$, there is a vertex not in $S$ joined to the vertices of $T$ and to no other vertices of $S$. Few explicit examples of 3-e.c. graphs are known, although almost all graphs are 3-e.c. We provide new examples of 3-e.c. graphs arising as incidence graphs of partial planes resulting from affine planes. We also present a new graph operation that preserves the 3-e.c. property.