A characterization of the components of the graphs \(D(k,q)\) (Q1924372): Difference between revisions

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)\).