|
Distance-transitive Graph
In the mathematical field of graph theory, a distance-transitive graph is a graph such that, given any two vertices and at any distance , and any other two vertices and at the same distance, there is an automorphism of the graph that carries to and to . Distance-transitive graphs were first defined in 1971 by Norman L. Biggs and D. H. Smith. A distance-transitive graph is interesting partly because it has a large automorphism group. Some interesting finite groups are the automorphism groups of distance-transitive graphs, especially of those whose diameter is 2. Examples Some first examples of families of distance-transitive graphs include: * The Johnson graphs. * The Grassmann graphs. * The Hamming Graphs. * The folded cube graphs. * The square rook's graphs. * The hypercube graphs. * The Livingstone graph. Classification of cubic distance-transitive graphs After introducing them in 1971, Biggs and Smith showed that there are only 12 finite trivalent ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 bipartite graph. Symmetry In 1932, Ronald M. Foster began collecting examples of cubic symmetric graphs, forming the start of the Foster census.. Many well-known individual graphs are cubic and symmetric, including the utility graph, the Petersen graph, the Heawood graph, the Möbius–Kantor graph, the Pappus graph, the Desargues graph, the Nauru graph, the Coxeter graph, the Tutte–Coxeter graph, the Dyck graph, the Foster graph and the Biggs–Smith graph. W. T. Tutte classified the symmetric cubic graphs by the smallest integer number ''s'' such that each two oriented paths of length ''s'' can be mapped to each other by exactly one symmetry of the graph. He showed that ''s'' is at most 5, and provided examples of graphs with each possible ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Desargues Graph
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. The name "Desargues graph" has also been used to refer to a ten-vertex graph, the complement of the Petersen graph, which can also be formed as the bipartite half of the 20-vertex Desargues graph. Constructions There are several different ways of constructing the Desargues graph: *It is the generalized Petersen graph . To form the Desargues graph in this way, connect ten of the vertices into a regular decagon, and connect the other ten vertices into a ten-pointed star that connects pairs of vertices at distance three in a second decagon. The Desargues graph consists of the 20 edges of these two polygons together with an additional 1 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Dodecahedral Graph
A regular dodecahedron or pentagonal dodecahedron is a dodecahedron that is regular, which is composed of 12 regular pentagonal faces, three meeting at each vertex. It is one of the five Platonic solids. It has 12 faces, 20 vertices, 30 edges, and 160 diagonals (60 face diagonals, 100 space diagonals). It is represented by the Schläfli symbol . Dimensions If the edge length of a regular dodecahedron is a, the radius of a circumscribed sphere (one that touches the regular dodecahedron at all vertices) is :r_u = a\frac \left(1 + \sqrt\right) \approx 1.401\,258\,538 \cdot a and the radius of an inscribed sphere (tangent to each of the regular dodecahedron's faces) is :r_i = a\frac \sqrt \approx 1.113\,516\,364 \cdot a while the midradius, which touches the middle of each edge, is :r_m = a\frac \left(3 +\sqrt\right) \approx 1.309\,016\,994 \cdot a These quantities may also be expressed as :r_u = a\, \frac \phi :r_i = a\, \frac :r_m = a\, \frac where ''ϕ'' is the golden rat ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Tutte–Coxeter Graph
In the mathematical field of graph theory, the Tutte–Coxeter graph or Tutte eight-cage or Cremona–Richmond graph is a 3-regular graph with 30 vertices and 45 edges. As the unique smallest cubic graph of girth 8, it is a cage and a Moore graph. It is bipartite, and can be constructed as the Levi graph of the generalized quadrangle ''W''2 (known as the Cremona–Richmond configuration). The graph is named after William Thomas Tutte and H. S. M. Coxeter; it was discovered by Tutte (1947) but its connection to geometric configurations was investigated by both authors in a pair of jointly published papers (Tutte 1958; Coxeter 1958a). All the cubic distance-regular graphs are known. The Tutte–Coxeter is one of the 13 such graphs. It has crossing number 13, book thickness 3 and queue number 2.Wolz, Jessica; ''Engineering Linear Layouts with SAT.'' Master Thesis, University of Tübingen, 2018 Constructions and automorphisms A particularly simple combinatorial construction of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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. Properties The Coxeter graph has chromatic number 3, chromatic index 3, radius 4, diameter 4 and girth 7. It is also a 3- vertex-connected graph and a 3- edge-connected graph. It has book thickness 3 and queue number 2. The Coxeter graph is hypohamiltonian: it does not itself have a Hamiltonian cycle but every graph formed by removing a single vertex from it is Hamiltonian. It has rectilinear crossing number 11, and is the smallest cubic graph with that crossing number . Construction The simplest construction of a Coxeter graph is from a Fano plane. Take the 7C3 = 35 possible 3-combinations on 7 objects. Discard the 7 triplets that correspond to the lines of the Fano plane, leaving 28 triplets. Link two triplets if they are disjoint. The result is the Coxete ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Pappus Graph
In the mathematical field of graph theory, the Pappus graph is a bipartite 3- regular undirected graph with 18 vertices and 27 edges, formed as the Levi graph of the Pappus configuration. It is named after Pappus of Alexandria, an ancient Greek mathematician who is believed to have discovered the "hexagon theorem" describing the Pappus configuration. All the cubic distance-regular graphs are known; the Pappus graph is one of the 13 such graphs. The Pappus graph has rectilinear crossing number 5, and is the smallest cubic graph with that crossing number . It has girth 6, diameter 4, radius 4, chromatic number 2, chromatic index 3 and is both 3- vertex-connected and 3- edge-connected. It has book thickness 3 and queue number 2. The Pappus graph has a chromatic polynomial equal to: (x-1)x(x^-26x^+325x^-2600x^+14950x^-65762x^+229852x^-653966x^9+1537363x^8-3008720x^7+4904386x^6-6609926x^5+7238770x^4-6236975x^3+3989074x^2-1690406x+356509). The name "Pappus graph" has also been used ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 of a surface is an upper bound for the number of colors that suffice to color any graph embedded in the surface. In 1890 Heawood proved for all surfaces ''except'' the sphere that no more than : H(S)=\left\lfl ... See also * Heywood (surname) {{surname ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cubical Graph
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 regular hexahedron and is one of the five Platonic solids. It has 6 faces, 12 edges, and 8 vertices. The cube is also a square parallelepiped, an equilateral cuboid and a right rhombohedron a 3-zonohedron. It is a regular square prism in three orientations, and a trigonal trapezohedron in four orientations. The cube is dual to the octahedron. It has cubical or octahedral symmetry. The cube is the only convex polyhedron whose faces are all squares. Orthogonal projections The ''cube'' has four special orthogonal projections, centered, on a vertex, edges, face and normal to its vertex figure. The first and third correspond to the A2 and B2 Coxeter planes. Spherical tiling The cube can also be represented as a spherical tiling, and pr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Petersen Graph
In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring. Although the graph is generally credited to Petersen, it had in fact first appeared 12 years earlier, in a paper by . Kempe observed that its vertices can represent the ten lines of the Desargues configuration, and its edges represent pairs of lines that do not meet at one of the ten points of the configuration. Donald Knuth states that the Petersen graph is "a remarkable configuration that serves as a counterexample to many optimistic predictions about what might be true for graphs in general." The Petersen graph also makes an appearance in tropical geometry. The cone over the Petersen graph is naturally identif ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Complete Bipartite Graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory itself is typically dated as beginning with Leonhard Euler's 1736 work on the Seven Bridges of Königsberg. However, drawings of complete bipartite graphs were already printed as early as 1669, in connection with an edition of the works of Ramon Llull edited by Athanasius Kircher. Llull himself had made similar drawings of complete graphs three centuries earlier.. Definition A complete bipartite graph is a graph whose vertices can be partitioned into two subsets and such that no edge has both endpoints in the same subset, and every possible edge that could connect vertices in different subsets is part of the graph. That is, it is a bipartite graph such that for every two vertices and, is an edge in . A complete bipartite graph w ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Complete Graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is connected by a pair of unique edges (one in each direction). Graph theory itself is typically dated as beginning with Leonhard Euler's 1736 work on the Seven Bridges of Königsberg. However, drawings of complete graphs, with their vertices placed on the points of a regular polygon, had already appeared in the 13th century, in the work of Ramon Llull. Such a drawing is sometimes referred to as a mystic rose. Properties The complete graph on vertices is denoted by . Some sources claim that the letter in this notation stands for the German word , but the German name for a complete graph, , does not contain the letter , and other sources state that the notation honors the contributions of Kazimierz Kuratowski to graph theory. has edges (a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
.svg "Click for more on -> Petersen Graph")
