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.
Reviewer: V.O.Groppen (Vladikaukaz)
MSC:
05C35 | Extremal problems in graph theory |
05B25 | Combinatorial aspects of finite geometries |
05C38 | Paths and cycles |
51E30 | Other finite incidence structures (geometric aspects) |