TOPICS
Search

Exact-Distance Hamming Graph


An exact-distance Hamming graph H_q(n,r) is the graph on words of length n over an alphabet of q symbols in which two words are adjacent precisely when their Hamming distance is r, where q, n, and r are integers with q>=2, n>=1, and 1<=r<=n. It is the graph distance graph at distance r of the Hamming graph H(n,q). In particular, H_q(n,1)=H(n,q), whereas larger exact distances generally give different graphs (Brešar et al. 2019). Each graph vertex has vertex degree (n; r)(q-1)^r, by choosing the positions that change and one of q-1 replacement symbols at each position.

Let T_q(n,r) be the largest number of vertices whose induced subgraph is a triangle-free graph. Csajbók et al. (2026) proved that T_q(n,1)=2q^(n-1) and T_q(n,2)=Theta_q(q^n/n) for every fixed integer q>=3. They also determined the exact order in the ternary distance-four case,

 T_3(n,4)=Theta((3^n)/(n^2)),

where Theta is big-Theta notation and the constants implicit in Theta_q may depend on q. The asymptotic estimates are for n->infty.


See also

Graph Distance Graph, Hamming Distance, Hamming Graph

Explore with Wolfram|Alpha

References

Brešar, B.; Gastineau, N.; Klavžar, S.; and Togni, O. "Exact Distance Graphs of Product Graphs." Graphs Combin. 35, 1555-1569, 2019. https://doi.org/10.1007/s00373-019-02089-0.Csajbók, B.; Mukkamala, P.; and Nagy, Z. L. "Triangle-Free Sets in Exact-Distance Hamming Graphs." 23 Oct 2026. https://arxiv.org/abs/2610.32789.

Cite this as:

Weisstein, Eric W. "Exact-Distance Hamming Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Exact-DistanceHammingGraph.html

Subject classifications