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

C. A. Baker1, Anthony Bonato2, Julia M.N. Brown3
1Department of Mathematics and Computer Science, 67 York Street, Sackville, Nb, Canaba, E4l 1E6
2Department of Mathematics, Wilfrid Laurier University, Water- Loo, on, Canaba, N2l 3C5
3Department Of Mathematics and Sratistics, York Universiry, N520 Ross Bul.Ding, 4700 Ker.E Stree’, Toronto, Ontario, Canada M3J 1p3

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.

Keywords: graph, geometry, adjacency property, n-e.c. graph, affine