|
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 group o ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Planar Graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points. Every graph that can be drawn on a plane can be drawn on the sphere as well, and vice versa, by means of stereographic projection. Plane graphs can be encoded by combinatorial maps or rotation systems. An equivalence class of topologically equivalent drawings on the sphere, usually with additional assumptions such as the absence of isthmuses, is called a pl ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Discrete Mathematics (journal)
''Discrete Mathematics'' is a biweekly peer-reviewed scientific journal in the broad area of discrete mathematics, combinatorics, graph theory, and their applications. It was established in 1971 and is published by North-Holland Publishing Company. It publishes both short notes, full length contributions, as well as survey articles. In addition, the journal publishes a number of special issues each year dedicated to a particular topic. Although originally it published articles in French and German, it now allows only English language articles. The editor-in-chief is Douglas West ( University of Illinois, Urbana). History The journal was established in 1971. The very first article it published was written by Paul Erdős, who went on to publish a total of 84 papers in the journal. Abstracting and indexing The journal is abstracted and indexed in: According to the ''Journal Citation Reports'', the journal has a 2020 impact factor of 0.87. Notable publications * The 1972 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Chvátal Graph
In the mathematical field of graph theory, the Chvátal graph is an undirected graph with 12 vertices and 24 edges, discovered by Václav Chvátal in 1970. It is the smallest graph that is triangle-free, 4-regular, and 4-chromatic. Coloring, degree, and girth The Chvátal graph is triangle-free: its girth (the length of its shortest cycle) is four. It is 4- regular: each vertex has exactly four neighbors. And its chromatic number is 4: it can be colored using four colors, but not using only three. It is, as Chvátal observes, the smallest possible 4-chromatic 4-regular triangle-free graph; the only smaller 4-chromatic triangle-free graph is the Grötzsch graph, which has 11 vertices but has maximum degree 5 and is not regular. By Brooks’ theorem, every k-regular graph (except for odd cycles and cliques) has chromatic number at most k. It was also known since that, for every k\ge 3 and \ell\ge 3 there exist k-chromatic graphs with girth \ell. In connection with these two r ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Induced Path
In the mathematical area of graph theory, an induced path in an undirected graph is a path that is an induced subgraph of . That is, it is a sequence of vertices in such that each two adjacent vertices in the sequence are connected by an edge in , and each two nonadjacent vertices in the sequence are not connected by any edge in . An induced path is sometimes called a snake, and the problem of finding long induced paths in hypercube graphs is known as the snake-in-the-box problem. Similarly, an induced cycle is a cycle that is an induced subgraph of ; induced cycles are also called chordless cycles or (when the length of the cycle is four or more) holes. An antihole is a hole in the complement of , i.e., an antihole is a complement of a hole. The length of the longest induced path in a graph has sometimes been called the detour number of the graph; for sparse graphs, having bounded detour number is equivalent to having bounded tree-depth. The induced path number of a graph ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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] |
Clebsch Graph
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 , who used it to evaluate the Ramsey number ''R''(3,3,3) = 17.. Construction The dimension-5 folded cube graph (the 5-regular Clebsch graph) may be constructed by adding edges between opposite pairs of vertices in a 4-dimensional hypercube graph. (In an ''n''-dimensional hypercube, a pair of vertices are ''opposite'' if the shortest path between them has ''n'' edges.) Alternatively, it can be formed from a 5-dime ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Induced Subgraph
In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Definition Formally, let G=(V,E) be any graph, and let S\subset V be any subset of vertices of . Then the induced subgraph G is the graph whose vertex set is S and whose edge set consists of all of the edges in E that have both endpoints in S . That is, for any two vertices u,v\in S , u and v are adjacent in G if and only if they are adjacent in G . The same definition works for undirected graphs, directed graphs, and even multigraphs. The induced subgraph G may also be called the subgraph induced in G by S , or (if context makes the choice of G unambiguous) the induced subgraph of S . Examples Important types of induced subgraphs include the following. *Induced paths are induced subgraphs that are paths. The shortest path between ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Regular Graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other. A regular graph with vertices of degree is called a graph or regular graph of degree . Also, from the handshaking lemma, a regular graph contains an even number of vertices with odd degree. Regular graphs of degree at most 2 are easy to classify: a graph consists of disconnected vertices, a graph consists of disconnected edges, and a graph consists of a disjoint union of cycles and infinite chains. A graph is known as a cubic graph. A strongly regular graph is a regular graph where every adjacent pair of vertices has the same number of neighbors in common, and every non-adjacent pair of vertices has the same number of neighbors in common. The smallest graphs that are regular but not strong ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Homomorphism
In the mathematical field of graph theory, a graph homomorphism is a mapping between two graphs that respects their structure. More concretely, it is a function between the vertex sets of two graphs that maps adjacent vertices to adjacent vertices. Homomorphisms generalize various notions of graph colorings and allow the expression of an important class of constraint satisfaction problems, such as certain scheduling or frequency assignment problems. The fact that homomorphisms can be composed leads to rich algebraic structures: a preorder on graphs, a distributive lattice, and a category (one for undirected graphs and one for directed graphs). The computational complexity of finding a homomorphism between given graphs is prohibitive in general, but a lot is known about special cases that are solvable in polynomial time. Boundaries between tractable and intractable cases have been an active area of research. Definitions In this article, unless stated otherwise, ''graphs'' are fi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Odd Girth
In graph theory, the girth of an undirected graph is the length of a shortest cycle contained in the graph. If the graph does not contain any cycles (that is, it is a forest), its girth is defined to be infinity. For example, a 4-cycle (square) has girth 4. A grid has girth 4 as well, and a triangular mesh has girth 3. A graph with girth four or more is triangle-free. Cages A cubic graph (all vertices have degree three) of girth that is as small as possible is known as a -cage (or as a -cage). The Petersen graph is the unique 5-cage (it is the smallest cubic graph of girth 5), the Heawood graph is the unique 6-cage, the McGee graph is the unique 7-cage and the Tutte eight cage is the unique 8-cage. There may exist multiple cages for a given girth. For instance there are three nonisomorphic 10-cages, each with 70 vertices: the Balaban 10-cage, the Harries graph and the Harries–Wong graph. Image:Petersen1 tiny.svg, The Petersen graph has a girth of 5 Image:Heawood_Graph ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Grötzsch's Theorem
In the mathematical field of graph theory, Grötzsch's theorem is the statement that every triangle-free planar graph can be colored with only three colors. According to the four-color theorem, every graph that can be drawn in the plane without edge crossings can have its vertices colored using at most four different colors, so that the two endpoints of every edge have different colors, but according to Grötzsch's theorem only three colors are needed for planar graphs that do not contain three mutually adjacent vertices. History The theorem is named after German mathematician Herbert Grötzsch, who published its proof in 1959. Grötzsch's original proof was complex. attempted to simplify it but his proof was erroneous.. In 2003, Carsten Thomassen derived an alternative proof from another related theorem: every planar graph with girth at least five is 3-list-colorable. However, Grötzsch's theorem itself does not extend from coloring to list coloring: there exist triangle-free ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
