Locally co-Heawood graphs
Andries E. Brouwer, Dmitri G. Fon-Der-Flaass, Sergey V. Shpectorov · Cambridge University Press eBooks · 1993
Let Δ be the incidence graph of the unique biplane on 7 points, that is, the bipartite complement of the Heawood graph. We find that there are precisely three connected graphs that are locally Δ, on 36, 48 and 108 vertices, where the last graph is an antipodal 3-cover of the first one. Introduction Let notation be as in [1]. (In particular, ∼ denotes adjacency, Γ i (γ) is the collection of vertices at distance i from γ in Γ, Γ(γ) := Γ 1 (γ), and γ ⊥ := {γ} ∪ Γ(γ).) The Heawood graph H is the smallest cubic graph of girth 6; it is bipartite, the incidence graph of the Fano plane. The co-Heawood graph Δ is its bipartite complement, the nonincidence graph of the Fano plane, i.e., the incidence graph of the unique biplane on 7 points. (Thus, Δ = H 3 .) The graph Δ has 14 vertices, valency 4, is bipartite, is distance-regular of diameter 3 and has distance distribution diagram Its automorphism group is G ≃ PGL (2, 7) of order 336 acting distance transitively. The graph Δ occurs in the Suzuki chain S 0 = 4 K 1 , S 1 = Δ, S 2 , S 3 , S 4 , S 5 of graphs on 4, 14, 36, 100, 416, 1782 vertices, respectively. Each graph S i+1 of this chain is locally S i . In particular, the graph Σ := S 2 is locally Δ, it is strongly regular with parameters ( v, k, λ, μ ) = (36,14,4,6).