Answers are grounded in this paper and cite their sources.
Theoretical analysis classifies edge- and distance-transitivity in Gilbert graphs and their complements, highlighting strict parameter separations and exact Lovász theta values.
The Gilbert graph Gq,n,d G q , n , d , which arises naturally in graph theory and coding theory, is the regular graph on Fqⁿ 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 Gq,n,d G q , n , d is edge-transitive or distance-transitive, and separately classify all parameters for which its complement has these properties. We prove that Gq,n,d G q , n , d is edge-transitive if and only if it is distance-transitive, and that this occurs precisely when $$d=2$$ d = 2 , $$(q,d)=(2,3)$$ ( q , d ) = ( 2 , 3 ) , or $$(q,d)=(2,n)$$ ( 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.
No takes yet. Share an insight, caveat, or question.
Krupnik et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: