Dejter graph

Last updated
Dejter graph
Dejter-Heawood4.pdf
Vertices 112
Edges 336
Radius 7
Diameter 7
Girth 4
Automorphisms 2688
Table of graphs and parameters
Red Ljubljana subgraph Dejter-Heawood1.pdf
Red Ljubljana subgraph
Blue Ljubljana subgraph Dejter-Heawood3.pdf
Blue Ljubljana subgraph
One seventh of the Dejter graph Dejter-Heawood2.pdf
One seventh of the Dejter graph

In the mathematical field of graph theory, the Dejter graph is a 6-regular graph with 112 vertices and 336 edges. [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. In particular, the Dejter graph admits a 3-factorization into two copies of the Ljubljana graph, which is the third smallest existing semi-symmetric cubic graph 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 {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 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.

Related Research Articles

Informally, the reconstruction conjecture in graph theory says that graphs are determined uniquely by their subgraphs. It is due to Kelly and Ulam.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

Heawood graph Undirected graph with 14 vertices

In the mathematical field of graph theory, the Heawood graph is an undirected graph with 14 vertices and 21 edges, named after Percy John Heawood.

Symmetric graph Graph in which all ordered pairs of linked nodes are automorphic

In the mathematical field of graph theory, a graph G is symmetric if, given any two pairs of adjacent vertices u1—v1 and u2—v2 of G, there is an automorphism

Desargues graph Distance-transitive cubic graph with 20 nodes and 30 edges

In the mathematical field of graph theory, the Desargues graph is a distance-transitive, cubic graph with 20 vertices and 30 edges. It is named after Girard Desargues, arises from several different combinatorial constructions, has a high level of symmetry, is the only known non-planar cubic partial cube, and has been applied in chemical databases.

Semi-symmetric graph Graph that is edge-transitive and regular but not vertex-transitive

In the mathematical field of graph theory, a semi-symmetric graph is an undirected graph that is edge-transitive and regular, but not vertex-transitive. In other words, a graph is semi-symmetric if each vertex has the same number of incident edges, and there is a symmetry taking any of the graph's edges to any other of its edges, but there is some pair of vertices such that no symmetry maps the first into the second.

<span class="mw-page-title-main">Hoffman–Singleton graph</span> 7-regular undirected graph with 50 nodes and 175 edges

In the mathematical field of graph theory, the Hoffman–Singleton graph is a 7-regular undirected graph with 50 vertices and 175 edges. It is the unique strongly regular graph with parameters (50,7,0,1). It was constructed by Alan Hoffman and Robert Singleton while trying to classify all Moore graphs, and is the highest-order Moore graph known to exist. Since it is a Moore graph where each vertex has degree 7, and the girth is 5, it is a (7,5)-cage.

Coxeter graph

In the mathematical field of graph theory, the Coxeter graph is a 3-regular graph with 28 vertices and 42 edges. It is one of the 13 known cubic distance-regular graphs. It is named after Harold Scott MacDonald Coxeter.

Hypercube graph Graphs formed by a hypercubes edges and vertices

In graph theory, the hypercube graphQn is the graph formed from the vertices and edges of an n-dimensional hypercube. For instance, the cube graph Q3 is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. Qn has 2n vertices, 2n – 1n edges, and is a regular graph with n edges touching each vertex.

Foster graph Bipartite 3-regular graph with 90 vertices and 135 edges

In the mathematical field of graph theory, the Foster graph is a bipartite 3-regular graph with 90 vertices and 135 edges.

Möbius–Kantor graph

In the mathematical field of graph theory, the Möbius–Kantor graph is a symmetric bipartite cubic graph with 16 vertices and 24 edges named after August Ferdinand Möbius and Seligmann Kantor. It can be defined as the generalized Petersen graph G(8,3): that is, it is formed by the vertices of an octagon, connected to the vertices of an eight-point star in which each point of the star is connected to the points three steps away from it.

In the mathematical field of graph theory, the Fibonacci cubes or Fibonacci networks are a family of undirected graphs with rich recursive properties derived from its origin in number theory. Mathematically they are similar to the hypercube graphs, but with a Fibonacci number of vertices. Fibonacci cubes were first explicitly defined in Hsu (1993) in the context of interconnection topologies for connecting parallel or distributed systems. They have also been applied in chemical graph theory.

Clebsch graph One of two different regular graphs with 16 vertices

In the mathematical field of graph theory, the Clebsch graph is either of two complementary graphs on 16 vertices, a 5-regular graph with 40 edges and a 10-regular graph with 80 edges. The 80-edge graph is the dimension-5 halved cube graph; it was called the Clebsch graph name by Seidel (1968) because of its relation to the configuration of 16 lines on the quartic surface discovered in 1868 by the German mathematician Alfred Clebsch. The 40-edge variant is the dimension-5 folded cube graph; it is also known as the Greenwood–Gleason graph after the work of Robert E. Greenwood and Andrew M. Gleason (1955), who used it to evaluate the Ramsey number R(3,3,3) = 17.

Ljubljana graph

In the mathematical field of graph theory, the Ljubljana graph is an undirected bipartite graph with 112 vertices and 168 edges.

Folded cube graph

In graph theory, a folded cube graph is an undirected graph formed from a hypercube graph by adding to it a perfect matching that connects opposite pairs of hypercube vertices.

In graph theory, a partial cube is a graph that is isometric to a subgraph of a hypercube. In other words, a partial cube can be identified with a subgraph of a hypercube in such a way that the distance between any two vertices in the partial cube is the same as the distance between those vertices in the hypercube. Equivalently, a partial cube is a graph whose vertices can be labeled with bit strings of equal length in such a way that the distance between two vertices in the graph is equal to the Hamming distance between their labels. Such a labeling is called a Hamming labeling; it represents an isometric embedding of the partial cube into a hypercube.

Italo Jose Dejter

Italo Jose Dejter is an Argentine-born American mathematician, a retired professor of mathematics and computer science from the University of Puerto Rico, and an active researcher in algebraic topology, differential topology, graph theory, coding theory and combinatorial designs. He obtained a Licentiate degree in mathematics from the University of Buenos Aires in 1967, arrived at Rutgers University in 1970 by means of a Guggenheim Fellowship and obtained a Ph.D. degree in mathematics in 1975 under the supervision of Professor Ted Petrie, with support of the National Science Foundation. He was a professor at the Federal University of Santa Catarina, Brazil, from 1977 to 1984, with grants from the National Council for Scientific and Technological Development, (CNPq).

Klein graphs

In the mathematical field of graph theory, the Klein graphs are two different but related regular graphs, each with 84 edges. Each can be embedded in the orientable surface of genus 3, in which they form dual graphs.

Halved cube graph Graph of the vertices and edges of a demihypercube

In graph theory, the halved cube graph or half cube graph of dimension n is the graph of the demihypercube, formed by connecting pairs of vertices at distance exactly two from each other in the hypercube graph. That is, it is the half-square of the hypercube. This connectivity pattern produces two isomorphic graphs, disconnected from each other, each of which is the halved cube graph.

110-vertex Iofinova-Ivanov graph

The 110-vertex Iofinova-Ivanov graph is, in graph theory, a semi-symmetric cubic graph with 110 vertices and 165 edges.

References

  1. ↑ Klin M.; Lauri J.; Ziv-Av M. "Links between two semisymmetric graphs on 112 vertices through the lens of association schemes", Jour. Symbolic Comput., 47–10, 2012, 1175–1191.
  2. ↑ Borges J.; Dejter I. J. "On perfect dominating sets in hypercubes and their complements", J. Combin. Math. Combin. Comput. 20 (1996), 161-173
  3. ↑ Dejter I. J. "On symmetric subgraphs of the 7-cube: an overview", Discrete Math. 124 (1994) 55–66
  4. ↑ Dejter I. J. "Symmetry of factors of the 7-cube Hamming shell", J. Combin. Des. 5 (1997), 301–309
  5. ↑ Dejter 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, 1991
  6. ↑ Dejter 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–32
  7. ↑ Dejter 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
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.