|
Helm Graph
This partial list of Graph (discrete mathematics), graphs contains definitions of graphs and graph families. For collected definitions of graph theory terms that do not refer to individual graph types, such as ''vertex'' and ''path'', see Glossary of graph theory. For links to existing articles about particular kinds of graphs, see :Graphs, 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 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph (discrete Mathematics)
In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a Set (mathematics), set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called ''Vertex (graph theory), vertices'' (also called ''nodes'' or ''points'') and each of the related pairs of vertices is called an ''edge'' (also called ''link'' or ''line''). Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges. The edges may be directed or undirected. For example, if the vertices represent people at a party, and there is an edge between two people if they shake hands, then this graph is undirected because any person ''A'' can shake hands with a person ''B'' only if ''B'' also shakes hands with ''A''. In contrast, if an edge from a person ''A'' to a person ''B'' means that ''A'' owes money to ''B'', then this graph is directed, because owing mon ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Franklin Graph
Franklin may refer to: People and characters * Franklin (given name), including list of people and characters with the name * Franklin (surname), including list of people and characters with the name * Franklin (class), a member of a historical English social class Places * Franklin (crater), a lunar impact crater * Franklin County (other), in a number of countries * Mount Franklin (other), including Franklin Mountain Australia * Franklin, Tasmania, a township * Division of Franklin, federal electoral division in Tasmania * Division of Franklin (state), state electoral division in Tasmania * Franklin, Australian Capital Territory, a suburb in the Canberra district of Gungahlin * Franklin River, river of Tasmania * Franklin Sound, waterway of Tasmania Canada * District of Franklin, a former district of the Northwest Territories * Franklin, Quebec, a municipality in the Montérégie region * Rural Municipality of Franklin, Manitoba * Franklin, Manitoba, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
McGee Graph
In the mathematics, 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 graph, 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 W. T. Tutte, 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-k-vertex-connected graph, vertex-connected and a 3-k-edge-connected graph, edge-connected graph. It has book t ... [...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 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 results relatin ... [...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 In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions shar .... Simpler counterexamples include the Errera graph 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 cub ... [...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. Despite not being vertex- or edge-transitive, the Hoffmann graph is still 1-walk-regular (but not distance-regular). The characteristic polynomial of the Hoffm ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Herschel Graph
In graph theory, a branch of mathematics, the Herschel graph is a bipartite graph, 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 (the three blue vertices aligned vertically in the center of the illustration) and eight vertices of degree three. Each two distinct degree-four vertices share two degree-three neighbors, forming a four-vertex cycle with these shared neighbors. There are three of these cycles, passing through six of the eight degree-three vertices (red in the illustration). Two more degree-three vertices (blue) do not participate in these four- ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Harries–Wong Graph
In the mathematical field of graph theory, the Harries–Wong graph is a 3-regular undirected graph with 70 vertices and 105 edges. The Harries–Wong graph has chromatic number 2, chromatic index 3, radius 6, diameter 6, girth 10 and is Hamiltonian. It is also a 3- vertex-connected and 3- edge-connected non-planar cubic graph. It has book thickness 3 and queue number In the mathematical field of graph theory, the queue number of a Graph (discrete mathematics), graph is a graph invariant defined analogously to book thickness, stack number (book thickness) using Queue (abstract data type), first-in first-out (q ... 2. The characteristic polynomial of the Harries–Wong graph is : (x-3) (x-1)^4 (x+1)^4 (x+3) (x^2-6) (x^2-2) (x^4-6x^2+2)^5 (x^4-6x^2+3)^4 (x^4-6x^2+6)^5. \, History In 1972, A. T. Balaban published a (3-10)-cage graph, a cubic graph that has as few vertices as possible for girth 10. It was the first (3-10)-cage discovered but it was not unique. The compl ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Harries Graph
In the mathematical field of graph theory, the Harries graph or Harries (3-10)-cage is a 3-regular, undirected graph with 70 vertices and 105 edges. The Harries graph has chromatic number 2, chromatic index 3, radius 6, diameter 6, girth 10 and is Hamiltonian. It is also a 3- vertex-connected and 3- edge-connected, non-planar, cubic graph. It has book thickness 3 and queue number 2. The characteristic polynomial of the Harries graph is : (x-3) (x-1)^4 (x+1)^4 (x+3) (x^2-6) (x^2-2) (x^4-6x^2+2)^5 (x^4-6x^2+3)^4 (x^4-6x^2+6)^5. \, History In 1972, A. T. Balaban published a (3-10)-cage graph, a cubic graph that has as few vertices as possible for girth 10. It was the first (3-10)-cage discovered but it was not unique. The complete list of (3-10)-cage and the proof of minimality was given by O'Keefe and Wong in 1980. There exist three distinct (3-10)-cage graphs—the Balaban 10-cage, the Harries graph and the Harries–Wong graph In the mathematical field of graph theory, t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Grötzsch Graph
In the mathematical field of graph theory, the Grötzsch graph is a triangle-free graph with 11 vertices, 20 edges, chromatic number 4, and crossing number 5. It is named after German mathematician Herbert Grötzsch, who used it as an example in connection with his 1959 theorem that planar triangle-free graphs are 3-colorable. The Grötzsch graph is a member of an infinite sequence of triangle-free graphs, each the Mycielskian of the previous graph in the sequence, starting from the one-edge graph; this sequence of graphs was constructed by to show that there exist triangle-free graphs with arbitrarily large chromatic number. Therefore, the Grötzsch graph is sometimes also called the Mycielski graph or the Mycielski–Grötzsch graph. Unlike later graphs in this sequence, the Grötzsch graph is the smallest triangle-free graph with its chromatic number. Properties The full automorphism group of the Grötzsch graph is isomorphic to the dihedral group D5 of order 10, the g ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
