On the Transitivity of Gilbert Graphs and their Complements

Source abstract

Abstract The Gilbert graph $$\mathcal {G}_{q,n,d}$$ G q , n , d , which arises naturally in graph theory and coding theory, is the regular graph on $$\mathbb {F}_q^n$$ 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 $$\mathcal {G}_{q,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 $$\mathcal {G}_{q,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 $$\vartheta$$ ϑ -function of Gilbert graphs, as well as of their complements, in all cases where either one of them is edge-transitive.