|
Heawood Family
In graph theory the term Heawood family refers to either one of the following two related graph families generated via ΔY- and YΔ-transformations: * the family of 20 graphs generated from the complete graph K_7. * the family of 78 graphs generated from K_7 and K_. In either setting the members of the graph family are collectively known as Heawood graphs, as the Heawood graph is a member. This is in analogy to the Petersen family, which too is named after its member the Petersen graph. The Heawood families are significant in topological graph theory. They contain the smallest known examples of intrinsically knotted graphs, of graphs that are not 4-flat, and of graphs with Colin de Verdière graph invariant \mu=6. The K_7-family The K_7-family is generated from the complete graph K_7 through repeated application of ΔY- and YΔ-transformations. The family consists of 20 graphs, all of which have 21 edges. The unique smallest member, K_7, has seven vertices. The unique large ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Heawood Graph
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. Combinatorial properties The graph is cubic, and all cycles in the graph have six or more edges. Every smaller cubic graph has shorter cycles, so this graph is the 6-cage, the smallest cubic graph of girth 6. It is a distance-transitive graph (see the Foster census) and therefore distance regular. Additions and Corrections to the book Distance-Regular Graphs (Brouwer, Cohen, Neumaier; Springer; 1989) There are 24 perfect matchings in the Heawood graph; for each matching, the set of edges not in the matching forms a Hamiltonian cycle. For instance, the figure shows the vertices of the graph placed on a cycle, with the internal diagonals of the cycle forming a matching. By subdividing the cycle edges into two matchings, we can partition the Heawood graph into three perfect matchings (that is, 3-color its edges) in eight different wa ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph theory), vertices'' (also called ''nodes'' or ''points'') which are connected by ''Glossary of graph theory terms#edge, edges'' (also called ''arcs'', ''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 (mathematics), set of vertices (also called nodes or points); * ... [...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 edg ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Petersen Family
In graph theory, the Petersen family is a set of seven undirected graphs that includes the Petersen graph and the complete graph . The Petersen family is named after Danish mathematician Julius Petersen, the namesake of the Petersen graph. Any of the graphs in the Petersen family can be transformed into any other graph in the family by YΔ- and ΔY-transformations, operations in which a triangle is replaced by a degree-three vertex or vice versa. These seven graphs form the forbidden minors for linklessly embeddable graphs, graphs that can be embedded into three-dimensional space in such a way that no two cycles in the graph are linked. They are also among the forbidden minors for the YΔY-reducible graphs. Definition The form of YΔ- and ΔY-transformations used to define the Petersen family is as follows: *If a graph contains a vertex with exactly three neighbors, then the YΔ-transform of at is the graph formed by removing from and adding edges between each pair of ... [...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 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Topological Graph Theory
In mathematics, topological graph theory is a branch of graph theory. It studies the embedding of graphs in surfaces, spatial embeddings of graphs, and graphs as topological spaces. It also studies immersions of graphs. Embedding a graph in a surface means that we want to draw the graph on a surface, a sphere for example, without two edges intersecting. A basic embedding problem often presented as a mathematical puzzle is the three utilities problem. Other applications can be found in printing electronic circuits where the aim is to print (embed) a circuit (the graph) on a circuit board (the surface) without two connections crossing each other and resulting in a short circuit. Graphs as topological spaces To an undirected graph we may associate an abstract simplicial complex ''C'' with a single-element set per vertex and a two-element set per edge. The geometric realization , ''C'', of the complex consists of a copy of the unit interval ,1per edge, with the endpoints ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Intrinsically Knotted Graph
In topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into three-dimensional Euclidean space in such a way that no two cycles of the graph are linked. A flat embedding is an embedding with the property that every cycle is the boundary of a topological disk whose interior is disjoint from the graph. A linklessly embeddable graph is a graph that has a linkless or flat embedding; these graphs form a three-dimensional analogue of the planar graphs.. Complementarily, an intrinsically linked graph is a graph that does not have a linkless embedding. Flat embeddings are automatically linkless, but not vice versa. The complete graph , the Petersen graph, and the other five graphs in the Petersen family do not have linkless embeddings. Every graph minor of a linklessly embeddable graph is again linklessly embeddable, as is every graph that can be reached from a linklessly embeddable graph by YΔ- and ΔY-transform ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Colin De Verdière Graph Invariant
Colin de Verdière's invariant is a graph parameter \mu(G) for any Graph (discrete mathematics), graph ''G,'' introduced by Yves Colin de Verdière in 1990. It was motivated by the study of the maximum multiplicity of the second eigenvalue of certain Schrödinger operators. Definition Let G=(V,E) be a simple graph with vertex set V=\. Then \mu(G) is the largest corank of any symmetric matrix M=(M_)\in\mathbb^ such that: * (M1) for all i,j with i\neq j: M_<0 if , and if ; * (M2) has exactly one negative eigenvalue, of multiplicity 1; * (M3) there is no nonzero matrix such that and such that if either or hold. Characterization of known graph families Several well-known families of graphs can be characterized in terms of their Colin de Verdièr ...[...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Complete Multipartite Graph
In graph theory, a part of mathematics, a -partite graph is a graph whose vertices are (or can be) partitioned into different independent sets. Equivalently, it is a graph that can be colored with colors, so that no two endpoints of an edge have the same color. When these are the bipartite graphs, and when they are called the tripartite graphs. Bipartite graphs may be recognized in polynomial time but, for any it is NP-complete, given an uncolored graph, to test whether it is -partite. However, in some applications of graph theory, a -partite graph may be given as input to a computation with its coloring already determined; this can happen when the sets of vertices in the graph represent different types of objects. For instance, folksonomies have been modeled mathematically by tripartite graphs in which the three sets of vertices in the graph represent users of a system, resources that the users are tagging, and tags that the users have applied to the resources. A comple ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
CW Complex
In mathematics, and specifically in topology, a CW complex (also cellular complex or cell complex) is a topological space that is built by gluing together topological balls (so-called ''cells'') of different dimensions in specific ways. It generalizes both manifolds and simplicial complexes and has particular significance for algebraic topology. It was initially introduced by J. H. C. Whitehead to meet the needs of homotopy theory. (open access) CW complexes have better categorical properties than simplicial complexes, but still retain a combinatorial nature that allows for computation (often with a much smaller complex). The C in CW stands for "closure-finite", and the W for "weak" topology. Definition CW complex A CW complex is constructed by taking the union of a sequence of topological spaces \emptyset = X_ \subset X_0 \subset X_1 \subset \cdots such that each X_k is obtained from X_ by gluing copies of k-cells (e^k_\alpha)_\alpha, each homeomorphic to the open k- bal ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
