|
Gallery Of Named Graphs
Some of the finite structures considered in graph theory have names, sometimes inspired by the graph's topology, and sometimes after their discoverer. A famous example is the Petersen graph, a concrete graph on 10 vertices that appears as a minimal example or counterexample in many different contexts. Individual graphs File:Balaban 10-cage alternative drawing.svg, Balaban 10-cage File:Balaban 11-cage.svg, Balaban 11-cage File:Bidiakis cube.svg, Bidiakis cube File:Brinkmann graph LS.svg, Brinkmann graph File:Bull graph.circo.svg, Bull graph File:Butterfly graph.svg, Butterfly graph File:Chvatal graph.draw.svg, Chvátal graph File:Diamond graph.svg, Diamond graph File:Dürer graph.svg, Dürer graph File:Ellingham-Horton 54-graph.svg, Ellingham–Horton 54-graph File:Ellingham-Horton 78-graph.svg, Ellingham–Horton 78-graph File:Errera graph.svg, Errera graph File:Franklin graph.svg, Franklin graph File:Frucht planar Lombardi.svg, Frucht graph File:Goldner-Harary graph.svg, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 connected by '' edges'' (also called ''links'' or ''lines''). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics. Definitions Definitions in graph theory vary. The following are some of the more basic ways of defining graphs and related mathematical structures. Graph In one restricted but very common sense of the term, a graph is an ordered pair G=(V,E) comprising: * V, a set of vertices (also called nodes or points); * E \subseteq \, a set of edges (also called links or lines), which are unordered pairs of vertices (that is, an edge is associated with t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Golomb Graph
In graph theory, the Golomb graph is a polyhedral graph with 10 vertices and 18 edges. It is named after Solomon W. Golomb, who constructed it (with a non-planar embedding) as a unit distance graph that requires four colors in any graph coloring. Thus, like the simpler Moser spindle, it provides a lower bound for the Hadwiger–Nelson problem: coloring the points of the Euclidean plane so that each unit line segment has differently-colored endpoints requires at least four colors. Construction The method of construction of the Golomb graph as a unit distance graph, by drawing an outer regular polygon connected to an inner twisted polygon or star polygon, has also been used for unit distance representations of the Petersen graph and of generalized Petersen graphs. As with the Moser spindle, the coordinates of the unit-distance embedding of the Golomb graph can be represented in the quadratic field \mathbbsqrt/math>. Fractional coloring The fractional chromatic number Fracti ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Sousselier Graph
The Sousselier graph is, in graph theory, a hypohamiltonian graph with 16 vertices and 27 edges. It has book thickness 3 and queue number In the mathematical field of graph theory, the queue number of a graph is a graph invariant defined analogously to stack number (book thickness) using first-in first-out (queue) orderings in place of last-in first-out (stack) orderings. Defi ... 2. History Hypohamiltonian graphs were first studied by Sousselier in ''Problèmes plaisants et délectables'' (1963) . In 1967, Lindgren builds an infinite sequence of hypohamiltonian graphs. The graphs of this sequence all have 6''k''+10 vertices, for every integer ''k''. The same sequence of hypohamiltonian graphs is independently built by Sousselier. In 1973 Chvátal explains in a scientific paper how edges can be added to some hypohamiltonian graphs in order to build new ones of the same order, and he names Bondy as the original author of the method. As an illustration, he shows that two ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Moser Spindle
In graph theory, a branch of mathematics, the Moser spindle (also called the Mosers' spindle or Moser graph) is an undirected graph, named after mathematicians Leo Moser and his brother William, with seven vertices and eleven edges. It is a unit distance graph requiring four colors in any graph coloring, and its existence can be used to prove that the chromatic number of the plane is at least four.. The Moser spindle has also been called the Hajós graph after György Hajós, as it can be viewed as an instance of the Hajós construction. However, the name "Hajós graph" has also been applied to a different graph, in the form of a triangle inscribed within a hexagon. Construction As a unit distance graph, the Moser spindle is formed by two rhombi with 60 and 120 degree angles, so that the sides and short diagonals of the rhombi form equilateral triangles. The two rhombi are placed in the plane, sharing one of their acute-angled vertices, in such a way that the remaining two acute ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Meredith Graph
In the mathematical field of graph theory, the Meredith graph is a 4- regular undirected graph with 70 vertices and 140 edges discovered by Guy H. J. Meredith in 1973. The Meredith graph is 4- vertex-connected and 4- edge-connected, has chromatic number 3, chromatic index 5, radius 7, diameter 8, girth 4 and is non-Hamiltonian. It has book thickness 3 and queue number 2. Published in 1973, it provides a counterexample to the Crispin Nash-Williams conjecture that every 4-regular 4-vertex-connected graph is Hamiltonian. However, W. T. Tutte showed that all 4-connected planar graphs are hamiltonian.Tutte, W.T., ed., Recent Progress in Combinatorics. Academic Press, New York, 1969. The characteristic polynomial of the Meredith graph is (x-4) (x-1)^ x^ (x+1)^ (x+3) (x^2-13) (x^6-26 x^4+3 x^3+169 x^2-39 x-45)^4. Gallery Image:Meredith graph 3COL.svg, The chromatic number of the Meredith graph is 3. Image:Meredith graph 5color edge.svg, The chromatic index In graph theory, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
McGee Graph
In the mathematical field of graph theory, the McGee graph or the (3-7)-cage is a 3-regular graph with 24 vertices and 36 edges. The McGee graph is the unique (3,7)-cage (the smallest cubic graph of girth 7). It is also the smallest cubic cage that is not a Moore graph. First discovered by Sachs but unpublished, the graph is named after McGee who published the result in 1960. Then, the McGee graph was proven the unique (3,7)-cage by Tutte in 1966. The McGee graph requires at least eight crossings in any drawing of it in the plane. It is one of three non-isomorphic graphs tied for being the smallest cubic graph that requires eight crossings. Another of these three graphs is the generalized Petersen graph , also known as the Nauru graph. The McGee graph has radius 4, diameter 4, chromatic number 3 and chromatic index 3. It is also a 3- vertex-connected and a 3- edge-connected graph. It has book thickness 3 and queue number 2. Algebraic properties The characteristic polynomial of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Erdős–Gyárfás Conjecture
In graph theory, the unproven Erdős–Gyárfás conjecture, made in 1995 by the prolific mathematician Paul Erdős and his collaborator András Gyárfás, states that every graph with minimum degree 3 contains a simple cycle whose length is a power of two. Erdős offered a prize of $100 for proving the conjecture, or $50 for a counterexample; it is one of many conjectures of Erdős. If the conjecture is false, a counterexample would take the form of a graph with minimum degree three having no power-of-two cycles. It is known through computer searches of Gordon Royle and Klas Markström that any counterexample must have at least 17 vertices, and any cubic counterexample must have at least 30 vertices. Markström's searches found four graphs on 24 vertices in which the only power-of-two cycles have 16 vertices. One of these four graphs is planar; however, the Erdős–Gyárfás conjecture is now known to be true for the special case of 3-connected cubic planar graphs Weaker resul ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Kittell Graph
In the mathematical field of graph theory, the Kittell graph is a planar graph with 23 vertices and 63 edges. Its unique planar embedding has 42 triangular faces. The Kittell graph is named after Irving Kittell, who used it as a counterexample to Alfred Kempe's flawed proof of the four-color theorem. Simpler counterexamples include the Errera graph In the mathematical field of graph theory, the Errera graph is a graph with 17 vertices and 45 edges. Alfred Errera published it in 1921 as a counterexample to Kempe's erroneous proof of the four color theorem; it was named after Errera by . Pro ... and Poussin graph (both published earlier than Kittell) and the Fritsch graph and Soifer graph. References Individual graphs Planar graphs {{graph-stub ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Horton Graph
In the mathematical field of graph theory, the Horton graph or Horton 96-graph is a 3-regular graph with 96 vertices and 144 edges discovered by Joseph Horton. Published by Bondy and Murty in 1976, it provides a counterexample to the Tutte conjecture that every cubic 3-connected bipartite graph is Hamiltonian. After the Horton graph, a number of smaller counterexamples to the Tutte conjecture were found. Among them are a 92 vertex graph by Horton published in 1982, a 78 vertex graph by Owens published in 1983, and the two Ellingham-Horton graphs (54 and 78 vertices). The first Ellingham-Horton graph was published by Ellingham in 1981 and was of order 78. At that time, it was the smallest known counterexample to the Tutte conjecture. The second one was published by Ellingham and Horton in 1983 and was of order 54. In 1989, Georges' graph, the smallest currently-known non-Hamiltonian 3-connected cubic bipartite graph was discovered, containing 50 vertices. As a non-Hamiltonian c ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Holt Graph
In graph theory, the Holt graph or Doyle graph is the smallest half-transitive graph, that is, the smallest example of a vertex-transitive and edge-transitive graph which is not also symmetric. Such graphs are not common. It is named after Peter G. Doyle and Derek F. Holt, who discovered the same graph independently in 1976 and 1981. respectively. The Holt graph has diameter 3, radius 3 and girth 5, chromatic number 3, chromatic index 5 and is Hamiltonian with distinct Hamiltonian cycles. It is also a 4- vertex-connected and a 4- edge-connected graph. It has book thickness 3 and queue number 3.Jessica Wolz, ''Engineering Linear Layouts with SAT''. Master Thesis, University of Tübingen, 2018 It has an automorphism group of order 54. This is a smaller group than a symmetric graph with the same number of vertices and edges would have. The graph drawing on the right highlights this, in that it lacks reflectional symmetry. The characteristic polynomial of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hoffman Graph
In the mathematical field of graph theory, the Hoffman graph is a 4-regular graph with 16 vertices and 32 edges discovered by Alan Hoffman. Published in 1963, it is cospectral to the hypercube graph Q4. The Hoffman graph has many common properties with the hypercube Q4—both are Hamiltonian and have chromatic number 2, chromatic index 4, girth 4 and diameter 4. It is also a 4- vertex-connected graph and a 4- edge-connected graph. However, it is not distance-regular. It has book thickness 3 and queue number 2.Jessica Wolz, ''Engineering Linear Layouts with SAT''. Master Thesis, University of Tübingen, 2018 Algebraic properties The Hoffman graph is not a vertex-transitive graph and its full automorphism group is a group of order 48 isomorphic to the direct product of the symmetric group S4 and the cyclic group Z/2Z. The characteristic polynomial of the Hoffman graph is equal to :(x-4) (x-2)^4 x^6 (x+2)^4 (x+4) making it an integral graph—a graph whose spectrum consists e ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Herschel Graph
In graph theory, a branch of mathematics, the Herschel graph is a bipartite undirected graph with 11 vertices and 18 edges. It is a polyhedral graph (the graph of a convex polyhedron), and is the smallest polyhedral graph that does not have a Hamiltonian cycle, a cycle passing through all its vertices. It is named after British astronomer Alexander Stewart Herschel, because of Herschel's studies of Hamiltonian cycles in polyhedral graphs (but not of this graph). Definition and properties The Herschel graph has three vertices of degree four and eight vertices of degree three. Each of the three pairs of degree-four vertices form a cycle of four vertices, in which they alternate with two of the degree-three vertices. Each of the two remaining degree-three vertices is adjacent to a degree-three vertex from each of these three cycles. The Herschel graph is a polyhedral graph; this means that it is a planar graph, one that can be drawn in the plane with none of its edges crossing, and ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
