In the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

field of

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, the Dejter graph is a 6-regular graph with 112 vertices and 336 edges.Borges J.; Dejter I. J. "On perfect dominating sets in hypercubes and their complements", J. Combin. Math. Combin. Comput. 20 (1996), 161-173Dejter I. J. "Symmetry of factors of the 7-cube Hamming shell", J. Combin. Des. 5 (1997), 301–309Dejter I. J.; Guan P. "Square-blocking edge subsets in hypercubes and vertex avoidance", Graph theory, combinatorics, algorithms, and applications (San Francisco, CA, 1989), 162–174, SIAM, Philadelphia, PA, 1991Dejter I. J.; Pujol J. "Perfect domination and symmetry in hypercubes", Proceedings of the Twenty-Sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, Florida, 1995). Congr. Numer. 111 (1995), 18–32Dejter I. J.; Weichsel P. M. "Twisted perfect dominating subgraphs of hypercubes", Proceedings of the Twenty-Fourth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, Florida, 1993). Congr. Numer. 94 (1993), 67–78 The Dejter graph is obtained by deleting a copy of the

Hamming code In computer science and telecommunication, Hamming codes are a family of linear error-correcting codes. Hamming codes can detect one-bit and two-bit errors, or correct one-bit errors without detection of uncorrected errors. By contrast, the sim ...

of length 7 from the binary 7-

cube In geometry, a cube is a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex. Viewed from a corner it is a hexagon and its net is usually depicted as a cross. The cube is the only r ...

. The Dejter graph, and by extension any graph obtained by deleting a

of length 2^r-1 from a (2^r-1)-

, is a

symmetric graph In the mathematical field of graph theory, a graph is symmetric (or arc-transitive) if, given any two pairs of adjacent vertices and of , there is an automorphism :f : V(G) \rightarrow V(G) such that :f(u_1) = u_2 and f(v_1) = v_2. In oth ...

. In particular, the Dejter graph admits a 3-

factorization In mathematics, factorization (or factorisation, see American and British English spelling differences#-ise, -ize (-isation, -ization), English spelling differences) or factoring consists of writing a number or another mathematical object as a p ...

into two copies of the

Ljubljana graph In the mathematical field of graph theory, the Ljubljana graph is an undirected bipartite graph with 112 vertices and 168 edges. It is a cubic graph with diameter 8, radius 7, chromatic number 2 and chromatic index 3. Its girth is 10 and there ...

, which is the third smallest existing semi-symmetric

cubic graph In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs. A bicubic graph is a cubic bipa ...

of regular degree 3. The Ljubljana graph has girth 10. In fact, it is proven that the Dejter graph can be 2-colored, say in the color set , as in the top figure to the right, so that both the resulting edge-monochromatic red and blue vertex-spanning subgraphs are copies of the

. These two copies contain exactly the 112 vertices of the Dejter graph and 168 edges each, having both copies girth 10, while the Dejter graph has girth 6 and the 7-cube girth 4. It seems that the Dejter graph is the smallest

having a connected self-complementary vertex-spanning semi-symmetric cubic subgraph. Both the red and blue vertex-spanning Ljubljana subgraphs of the Dejter graph can be presented as

covering graph In the mathematical discipline of graph theory, a graph is a covering graph of another graph if there is a covering map from the vertex set of to the vertex set of . A covering map is a surjection and a local isomorphism: the neighbourhood of ...

s of the

Heawood graph Heawood is a surname. Notable people with the surname include: *Jonathan Heawood, British journalist *Percy John Heawood (1861–1955), British mathematician **Heawood conjecture **Heawood graph **Heawood number In mathematics, the Heawood number ...

, namely as 8-covers of the

. This is suggested in each of the two representations of the

, (red above, blue below, both to the right), by alternately coloring the inverse images of successive vertices of the

, say in black and white (better viewed by twice clicking on images for figure enlargements), according to the

bipartition. Each such inverse image is formed by the 8 neighbors, along a fixed coordinate direction of the 7-cube, of the half of the Hamming code having a fixed weight, 0 or 1. By exchanging these weights via the permutation (0 1), one can pass from the adjacency offered by the red Ljubljana graph to the one offered by the blue Ljubljana graph, or vice versa. One seventh of the Dejter graph appears in a separate figure down below that can be obtained from the two resulting copies of the

References

{{reflist , refs= Individual graphs Regular graphs