Paper

On the transitivity of Gilbert graphs and their complements

Sason, Igal, Berman, Abraham, Krupnik, Noam

2026

Overview

The Gilbert graph \\(Gilbert(q,n,d)\\), which arises naturally in graph theory and coding theory, is the regular graph on \\(F_q^n\\) in which two vertices are adjacent if their Hamming distance is less than \\(d\\), and it is vertex-transitive. We classify all parameters \\((q,n,d)\\) for which \\(Gilbert(q,n,d)\\) is edge-transitive or distance-transitive, and separately classify all parameters for which its complement has these properties. We prove that \\(Gilbert(q,n,d)\\) is edge-transitive if and only if it is distance-transitive, and that this occurs precisely when \\(d=2\\), \\((q,d)=(2,3)\\), or \\((q,d)=(2,n)\\). For the complement graphs, we determine all parameters yielding edge- or distance-transitivity using spectral methods based on Krawtchouk polynomials and the structure of the Hamming association scheme. In contrast to the Gilbert graphs, where the parameter sets corresponding to edge- and distance-transitivity coincide, we show that for their complements the set of parameters yielding distance-transitivity is strictly contained in the set yielding edge-transitivity. As an application, we compute the exact values of the Lovász \\(\\)-function of Gilbert graphs, as well as of their complements, in all cases where either one of them is edge-transitive.

• Publisher: Cornell University Library, arXiv.org
• Subject: Apexes / Classification / Graph theory / Graphs / Parameters / Polynomials / Spectral methods