Talk:Hamming graph

For the Hamming (3,3) graph, the vertical coordinates are roots of polynomial 3 x^6 - 9 x^4 + 6 x^2 - 1 = 0. Use the 6th, 5th, and negative 4th roots, for approximate values {1.4619, 0.777862, -0.507713}. EdPeggJr (talk) 22:12, 26 October 2016 (UTC)

Example with invertible binary matrices (actually not)

Hamming graph of invertible binary 3×3 matrices
(This is one component, and all determinants are positive. The other component contains the reflections with negative determinant.)

To me this seems like a good example of a Hamming graph, but I am not sure. Maybe someone wants to include it. --Watchduck (quack) 01:18, 30 December 2021 (UTC)

Hamming graphs must include a vertex for every possible d-tuple of elements of the underlying set, and an edge for every way of changing one element of the tuple to get another tuple. It's not obvious that the graph you show here has those properties. The invertible 3x3 matrices do not form a Hamming graph, at least not in the obvious way, for one thing because not all $2^{9}$ binary 3x3 matrices are invertible, so you're not including all the vertices that you need to include, for another because Hamming graphs are automatically connected, so what your caption says about connected components makes no sense in this context, and for a third because Hamming graphs are automatically regular and vertex-transitive and this doesn't appear to be. What makes you think that this is a Hamming graph? —David Eppstein (talk) 02:05, 30 December 2021 (UTC)

Oops, that was wishful thinking on my part. "Two vertices are adjacent if they differ in precisely one coordinate; that is, if their Hamming distance is one." was what I was looking for. I overlooked the more specific requirements, like the number of vertices. (My graph has 168.) --Watchduck (quack) 14:32, 30 December 2021 (UTC)

A graph with 168 vertices can only be a Hamming graph if it is a complete graph, because 168 is not a power of any smaller number. —David Eppstein (talk) 18:03, 30 December 2021 (UTC)

The lead image is wrong

Wackystan I've never flagged this kind of thing before, not sure the right way to do it. But the image here is incorrect. H(3,3) should be a 6-regular graph, but the innermost circle of vertices here all have degree 8. — Preceding undated comment added 06:17, 17 September 2024 (UTC)

I believe the apparent lines of four vertices consist of only two overlapping edges. It is labeled as a unit distance graph, and for vertices 1-2-3-4 along one of these lines only 1-3 and 2-4 are at the same distance as the lengths of the other edges. It is unfortunate as an illustration of a graph to have this ambiguity but perhaps the edge overlap is necessary for its representation as a unit graph or to maintain symmetry. In unit graphs, this sort of overlap is not forbidden. —David Eppstein (talk) 07:20, 17 September 2024 (UTC)