Explicit construction of graphs with an arbitrary large girth and of large size
For any power \(q= p^n\) of any prime \(p\), the authors construct a flag-transitive semiplane, \(\Gamma(q)\), whose points and lines are infinite sequences of elements of the \(q\)-element field; for integers \(k\geq 2\), an incidence system \(\Gamma(k, q)\) is defined from \(\Gamma(q)\) by ``projection'' on the first \(k\) coordinates; \(D(q)\) and \(D(k, q)\) are, respectively, the incidence graphs of \(\Gamma(q)\) and \(\Gamma(k, q)\). The graphs \(D(q)\) and \(D(k, q)\) are bipartite, regular of degree \(q\), and edge-transitive; \(D(k, q)\) has \(2q^k\) vertices; \(D(2^n)\) and, for even \(k\), \(D(k, 2^n)\) are vertex-transitive. For positive odd integers \(k\geq 3\) the girth of \(D(k,q)\) is at least \(k+ 5\). ``The construction was motivated by some results on embeddings of Chevalley group geometries in the corresponding Lie algebras, and the notion of a covering of a graph''.
scientific article; zbMATH DE number 777831
scientific article