|
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) ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Pappus Graph LS
Pappus may refer to: * Pappus (botany), a structure within certain flowers * ''Pappus'' (bug), a genus of insects in the tribe Mirini * Pappus of Alexandria, Greek mathematician ** Pappus's hexagon theorem, often just called 'Pappus's theorem', a theorem named for Pappus of Alexandria ** Pappus's centroid theorem, another theorem named for Pappus of Alexandria ** Pappus configuration, a geometric configuration related to 'Pappus's theorem' ** Pappus graph, a graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ... related to the pappus configuration See also * Papus (other) * Pappu, an Indian male given name ** Pappu (cinematographer) (1977–2022), Indian cinematographer * ''Pappu'' (film), 1980 Indian film {{disambiguation ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Distance-regular Graph
In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two vertices and , the number of vertices at distance from and at distance from depends only upon , , and the distance between and . Some authors exclude the complete graphs and disconnected graphs from this definition. Every distance-transitive graph is distance regular. Indeed, distance-regular graphs were introduced as a combinatorial generalization of distance-transitive graphs, having the numerical regularity properties of the latter without necessarily having a large automorphism group. Intersection arrays The intersection array of a distance-regular graph is the array ( b_0, b_1, \ldots, b_; c_1, \ldots, c_d ) in which d is the diameter of the graph and for each 1 \leq j \leq d , b_j gives the number of neighbours of u at distance j+1 from v and c_j gives the number of neighbours of u at distance j - 1 from v for any pair of vertices u and v at dis ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Regular Map (graph Theory)
In mathematics, a regular map is a symmetric tessellation of a closed surface (topology), surface. More precisely, a regular map is a Manifold decomposition, decomposition of a two-dimensional manifold (such as a sphere, torus, or real projective plane) into topological disks such that every Flag (geometry), flag (an incident vertex-edge-face triple) can be transformed into any other flag by a automorphism group, symmetry of the decomposition. Regular maps are, in a sense, topological generalizations of Platonic solids. The theory of maps and their classification is related to the theory of Riemann surfaces, hyperbolic geometry, and Galois theory. Regular maps are classified according to either: the genus (mathematics), genus and orientability of the supporting surface, the Graph embedding, underlying graph, or the automorphism group. Overview Regular maps are typically defined and studied in three ways: topologically, group-theoretically, and graph-theoretically. Topologica ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Petrie Dual
In topological graph theory, the Petrie dual of an graph embedding, embedded graph (on a 2-manifold with all faces disks) is another embedded graph that has the Petrie polygons of the first embedding as its faces. The Petrie dual is also called the Petrial, and the Petrie dual of an embedded graph G may be denoted G^\pi. It can be obtained from a signed rotation system or ribbon graph representation of the embedding by twisting every edge of the embedding. Properties Like the usual dual graph, repeating the Petrie dual operation twice returns to the original surface embedding. Unlike the usual dual graph (which is an embedding of a generally different graph in the same surface) the Petrie dual is an embedding of the same graph in a generally different surface. Surface duality and Petrie duality are two of the six Wilson operations, and together generate the group of these operations. Regular polyhedra Applying the Petrie dual to a regular polyhedron produces a regular map (graph ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Triangle Graph
In the mathematical field of graph theory, the triangle graph is a planar undirected graph with 3 vertices and 3 edges, in the form of a triangle. The triangle graph is also known as the cycle graph C_3 and the complete graph K_3. Properties The triangle graph has chromatic number 3, chromatic index 3, radius 1, diameter 1 and girth 3. It is also a 2- vertex-connected graph and a 2- edge-connected graph. Its chromatic polynomial is (x-2)(x-1)x. See also * Triangle-free graph In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with ... References {{reflist Individual graphs Regular graphs ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Complement Graph
In the mathematical field of graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in . That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and removes all the edges that were previously there.. The complement is not the set complement of the graph; only the edges are complemented. Definition Let be a simple graph and let consist of all 2-element subsets of . Then is the complement of , where is the relative complement of in . For directed graphs, the complement can be defined in the same way, as a directed graph on the same vertex set, using the set of all 2-element ordered pairs of in place of the set in the formula above. In terms of the adjacency matrix ''A'' of the graph, if ''Q'' is the adjacency matrix of the complete graph of the same number of vertices (i.e. all entries ar ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Chromatic Polynomial
The chromatic polynomial is a graph polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was originally defined by George David Birkhoff to study the four color problem. It was generalised to the Tutte polynomial by Hassler Whitney and W. T. Tutte, linking it to the Potts model of statistical physics. History George David Birkhoff introduced the chromatic polynomial in 1912, defining it only for planar graphs, in an attempt to prove the four color theorem. If P(G, k) denotes the number of proper colorings of ''G'' with ''k'' colors then one could establish the four color theorem by showing P(G, 4)>0 for all planar graphs ''G''. In this way he hoped to apply the powerful tools of analysis and algebra for studying the roots of polynomials to the combinatorial coloring problem. Hassler Whitney generalised Birkhoff’s polynomial from the planar case to general graphs in 1932. In ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 (queue) orderings in place of Stack (abstract data type), last-in first-out (stack) orderings. Definition A queue layout of a given graph is defined by a total ordering of the vertex (graph theory), vertices of the graph together with a partition of the edge (graph theory), edges into a number of "queues". The set of edges in each queue is required to avoid edges that are properly nested: if and are two edges in the same queue, then it should not be possible to have in the vertex ordering. The queue number of a graph is the minimum number of queues in a queue layout.. Equivalently, from a queue layout, one could process the edges in a single queue using a Queue (abstract data type), queue data structure, by considering the vertices in ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Book Thickness
In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings in a ''book'', a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie on this boundary line, called the ''spine'', and the edges are required to stay within a single half-plane. The book thickness of a graph is the smallest possible number of half-planes for any book embedding of the graph. Book thickness is also called pagenumber, stacknumber or fixed outerthickness. Book embeddings have also been used to define several other graph invariants including the pagewidth and book crossing number. Every graph with vertices has book thickness at most \lceil n/2\rceil, and this formula gives the exact book thickness for complete graphs. The graphs with book thickness one are the outerplanar graphs. The graphs with book thickness at most two are the subhamiltonian graphs, which are always planar; more generally, e ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
K-edge-connected Graph
In graph theory, a connected graph is -edge-connected if it remains connected whenever fewer than edges are removed. The edge-connectivity of a graph is the largest for which the graph is -edge-connected. Edge connectivity and the enumeration of -edge-connected graphs was studied by Camille Jordan in 1869. Formal definition Let G = (V, E) be an arbitrary graph. If the subgraph G' = (V, E \setminus X) is connected for all X \subseteq E where , X, < k, then ''G'' is said to be ''k''-edge-connected. The edge connectivity of is the maximum value ''k'' such that ''G'' is ''k''-edge-connected. The smallest set ''X'' whose removal disconnects ''G'' is a minimum cut in ''G''. The edge connectivity version of Menger's theorem provides an alternative and equivalent character ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
K-vertex-connected Graph
In graph theory, a connected Graph (discrete mathematics), graph is said to be -vertex-connected (or -connected) if it has more than Vertex (graph theory), vertices and remains Connectivity (graph theory), connected whenever fewer than vertices are removed. The vertex-connectivity, or just connectivity, of a graph is the largest for which the graph is -vertex-connected. Definitions A graph (other than a complete graph) has connectivity ''k'' if ''k'' is the size of the smallest subset of vertices such that the graph becomes disconnected if you delete them. In complete graphs, there is no subset whose removal would disconnect the graph. Some sources modify the definition of connectivity to handle this case, by defining it as the size of the smallest subset of vertices whose deletion results in either a disconnected graph or a single vertex. For this variation, the connectivity of a complete graph K_n is n-1. An equivalent definition is that a graph with at least two vertic ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Chromatic Index
In graph theory, a proper edge coloring of a Graph (discrete mathematics), graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most different colors, for a given value of , or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three. By Vizing's theorem, the number of colors needed to edge color a simple graph is either its maximum Degree (graph theory), degree or . For some graphs, such as bip ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
