Explicit construction of graphs with an arbitrary large girth and of large size
type: Item
instance of: scholarly article
title: Explicit construction of graphs with an arbitrary large girth and of large size
zbMATH Open document ID: 0840.05045
DOI: 10.1016/0166-218X(94)00058-L
author: Felix Lazebnik
author: V. A. Ustimenko
published in: Discrete Applied Mathematics
publication date: 1995-09-06T00:00:00Z
review text: 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''.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05B30
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 51E30
zbMATH DE Number: 777831
zbMATH Keywords: flag-transitive semiplane
zbMATH Keywords: incidence system
zbMATH Keywords: incidence graphs
zbMATH Keywords: vertex-transitive
zbMATH Keywords: girth
zbMATH Keywords: Chevalley group geometries
zbMATH Keywords: Lie algebras
zbMATH Keywords: covering
reviewed by: William G. Brown
MaRDI profile type: Publication
cites work: Minimal Regular Graphs of Girths Eight and Twelve
cites work: Q3588187
cites work: Q3794212
cites work: Note on the girth of Ramanujan graphs
cites work: The sextet construction for cubic graphs
cites work: Q3852212
cites work: Cycles of even length in graphs
cites work: Q3992965
cites work: Q3976404
cites work: On a class of degenerate extremal graph problems
cites work: Explicit construction of regular graphs without small cycles
cites work: Q3733675
cites work: New examples of graphs without small cycles and of large size
cites work: Ramanujan graphs
cites work: Explicit constructions of graphs without short cycles and low density codes
cites work: Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
cites work: Q3312262
cites work: Q3485077
cites work: Q4854355
cites work: Girths of bipartite sextet graphs
cites work: Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
description: scientific article; zbMATH DE number 777831