| 词条 | Dejter graph |
| 释义 |
| name = Dejter graph | image = Dejter-Heawood4.pdf | vertices = 112 | edges = 336 | automorphisms = 2688 | girth = 4 | diameter = 7 | radius = 7 }} In the mathematical field of graph theory, the Dejter graph is a 6-regular graph with 112 vertices, 336 edges and girth 4.[1][2][3][4][5][6][7] The Dejter graph is obtained by deleting a copy of the Hamming code of length 7 from the binary 7-cube. The Dejter graph, and by extension any graph obtained by deleting a Hamming code of length 2r-1 from a (2r-1)-cube, is a symmetric graph (and so it is both vertex-transitive and edge-transitive but is not half-transitive). In particular, the Dejter graph admits a 3-factorization into two copies of the Ljubljana graph, which is the third smallest existing edge- but not vertex-transitive graph of regular degree 3, also called a semi-symmetric cubic graph. In fact, it is proven that the Dejter graph can be 2-colored, say in the color set {red, blue}, 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 Ljubljana graph. 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 symmetric graph having a connected self-complementary vertex-spanning semi-symmetric cubic subgraph. Both the red and blue vertex-spanning Ljubljana subgraphs of the drawn Dejter graph can be presented as covering graphs of the Heawood graph, namely as 8-covers of the Heawood graph. This is suggested in each of the two representations of the Ljubljana graph, (red above, blue below, both to the right), by alternately coloring the inverse images of successive vertices of the Heawood graph, say in black and white (better viewed by twice clicking on images for figure enlargements), according to the Heawood graph 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 Heawood graph. References1. ^Klin M.; Lauri J.; Ziv-Av M. "Links between two semisymmetric graphs on 112vertices through the lens of association schemes", Jour. SymbolicComput., 47–10, 2012, 1175–1191. 2. ^Borges J.; Dejter I. J. "On perfect dominating sets inhypercubes and their complements", J. Combin. Math. Combin. Comput.20 (1996), 161-173 3. ^Dejter I. J. "On symmetric subgraphsof the 7-cube: an overview", Discrete Math. 124 (1994) 55–66 4. ^Dejter I. J. "Symmetry of factors of the 7-cube Hammingshell", J. Combin. Des. 5 (1997), 301–309 5. ^Dejter I. J.;Guan P. "Square-blocking edge subsets in hypercubes and vertexavoidance", Graph theory, combinatorics, algorithms, andapplications (San Francisco, CA, 1989), 162–174, SIAM, Philadelphia,PA, 1991 6. ^Dejter I. J.; Pujol J. "Perfect domination and symmetry in hypercubes", Proceedings of the Twenty-sixthSoutheastern International Conference on Combinatorics, Graph Theoryand Computing (Boca Raton, Florida, 1995). Congr. Numer. 111 (1995),18–32 7. ^Dejter I. J.; Weichsel P. M. "Twisted perfectdominating subgraphs of hypercubes", Proceedings of theTwenty-fourth Southeastern International Conference onCombinatorics, Graph Theory, and Computing (Boca Raton, Florida, 1993).Congr. Numer. 94 (1993), 67–78 2 : Individual graphs|Regular graphs |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。