×

Girth 5 graphs from elliptic semiplanes. (English) Zbl 1248.05089

For \(3\leq k\leq 20\) with \(k\neq 4, 8, 12\), all the smallest currently known \(k\)-regular graphs of girth 5 have the same orders as the girth 5 graphs obtained by the following construction: take a (not necessarily Desarguesian) elliptic semiplane \(\mathcal S\) of order \(n - 1\) where \(n = k - r\) for some \(r\geq 1\); the Levi graph \(\Gamma (\mathcal S)\) of \(\mathcal S\) is an \(n\)-regular graph of girth 6; parallel classes of \(\mathcal S\) induce co-liques in \(\Gamma (\mathcal S)\), some of which are eventually deleted; the remaining co-liques are amalgamated with suitable \(r\)-regular graphs of girth at least 5. For \(k > 20\), this construction yields some new instances underbidding the smallest orders known so far. The paper contains three lemmas, two theorems, three definitions , seven illustrating examples and 31 references. All equations, figures and tables presented in the paper are not enumerated.

MSC:

05C35 Extremal problems in graph theory
05B25 Combinatorial aspects of finite geometries
05C38 Paths and cycles
51E30 Other finite incidence structures (geometric aspects)