A characterization of the components of the graphs \(D(k,q)\)
type: Item
instance of: scholarly article
title: A characterization of the components of the graphs \(D(k,q)\)
zbMATH Open document ID: 0861.05051
DOI: 10.1016/S0012-365X(96)83019-6
author: Felix Lazebnik
author: V. A. Ustimenko
author: Andrew J. Woldar
published in: Discrete Mathematics
publication date: 1997-05-04T00:00:00Z
review text: The graphs \(D(k,q)\) first arose in the context of extremal graph theory because of their large girth. Each graph \(D(k,q)\) is \(q\)-regular, bipartite, of order \(2q^k\), of girth at least \(k+5\) (for \(k\) odd), and its automorphism group is transitive on each of its bipartition sets as well as on its set of edges. This paper proves that \(D(k,q)\) has at least \(q^{t-1}\) components (where \(t=\lfloor{k+2\over 4}\rfloor\)) and completely characterizes the structure of \(D(k,q)\).
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 935384
zbMATH Keywords: characterization
zbMATH Keywords: graphs \(D(k,q)\)
zbMATH Keywords: extremal graph
zbMATH Keywords: girth
zbMATH Keywords: automorphism group
zbMATH Keywords: components
MaRDI profile type: Publication
cites work: Q3794212
cites work: Q3852212
cites work: Graphs of prescribed girth and bi-degree
cites work: Explicit construction of graphs with an arbitrary large girth and of large size
cites work: New examples of graphs without small cycles and of large size
cites work: A new series of dense graphs of high girth
cites work: Ramanujan graphs
cites work: Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
cites work: Q4863514
description: scientific article; zbMATH DE number 935384