In graph theory, a book graph (often written ) may be any of several kinds of graph formed by multiple cycles sharing an edge.
In graph theory, a book graph (often written ) may be any of several kinds of graph formed by multiple cycles sharing an edge.
One kind, which may be called a quadrilateral book, consists of p quadrilaterals sharing a common edge (known as the "spine" or "base" of the book). That is, it is a Cartesian product of a star and a single edge. [1] [2] The 7-page book graph of this type provides an example of a graph with no harmonious labeling. [2]
A second type, which might be called a triangular book, is the complete tripartite graph K1,1,p. It is a graph consisting of triangles sharing a common edge. [3] A book of this type is a split graph. This graph has also been called a [4] or a thagomizer graph (after thagomizers, the spiked tails of stegosaurian dinosaurs, because of their pointy appearance in certain drawings) and their graphic matroids have been called thagomizer matroids. [5] Triangular books form one of the key building blocks of line perfect graphs. [6]
The term "book-graph" has been employed for other uses. Barioli [7] used it to mean a graph composed of a number of arbitrary subgraphs having two vertices in common. (Barioli did not write for his book-graph.)
Given a graph , one may write for the largest book (of the kind being considered) contained within .
Denote the Ramsey number of two triangular books by This is the smallest number such that for every -vertex graph, either the graph itself contains as a subgraph, or its complement graph contains as a subgraph.
In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say, blue and red), let r and s be any two positive integers. Ramsey's theorem states that there exists a least positive integer R(r, s) for which every blue-red edge colouring of the complete graph on R(r, s) vertices contains a blue clique on r vertices or a red clique on s vertices. (Here R(r, s) signifies an integer that depends on both r and s.)
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being in terms of: independent sets; bases or circuits; rank functions; closure operators; and closed sets or flats. In the language of partially ordered sets, a finite simple matroid is equivalent to a geometric lattice.
In graph theory, a proper edge coloring of a 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 k different colors, for a given value of k, 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.
In the mathematical theory of matroids, a graphic matroid is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called co-graphic matroids or bond matroids. A matroid that is both graphic and co-graphic is sometimes called a planar matroid ; these are exactly the graphic matroids formed from planar graphs.
The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning forests needed to cover all the edges of the graph. The Nash-Williams theorem provides necessary and sufficient conditions for when a graph is k-arboric.
In mathematics, Paley graphs are dense undirected graphs constructed from the members of a suitable finite field by connecting pairs of elements that differ by a quadratic residue. The Paley graphs form an infinite family of conference graphs, which yield an infinite family of symmetric conference matrices. Paley graphs allow graph-theoretic tools to be applied to the number theory of quadratic residues, and have interesting properties that make them useful in graph theory more generally.
In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these graphs from a broader definition that allows some non-adjacent pairs of vertices to be at distance one, they may also be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs. The unit distance graphs include the cactus graphs, the matchstick graphs and penny graphs, and the hypercube graphs. The generalized Petersen graphs are non-strict unit distance graphs.
In graph theory, a mathematical discipline, a factor-critical graph is a graph with n vertices in which every subgraph of n − 1 vertices has a perfect matching.
In graph theory, a cactus is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple cycle, or in which every block is an edge or a cycle.
In extremal graph theory, the Erdős–Stone theorem is an asymptotic result generalising Turán's theorem to bound the number of edges in an H-free graph for a non-complete graph H. It is named after Paul Erdős and Arthur Stone, who proved it in 1946, and it has been described as the “fundamental theorem of extremal graph theory”.
In graph theory, a peripheral cycle in an undirected graph is, intuitively, a cycle that does not separate any part of the graph from any other part. Peripheral cycles were first studied by Tutte (1963), and play important roles in the characterization of planar graphs and in generating the cycle spaces of nonplanar graphs.
For a graph, a maximum cut is a cut whose size is at least the size of any other cut. That is, it is a partition of the graph's vertices into two complementary sets S and T, such that the number of edges between S and T is as large as possible. Finding such a cut is known as the max-cut problem.
In extremal graph theory, the forbidden subgraph problem is the following problem: given a graph , find the maximal number of edges an -vertex graph can have such that it does not have a subgraph isomorphic to . In this context, is called a forbidden subgraph.
Jon Hal Folkman was an American mathematician, a student of John Milnor, and a researcher at the RAND Corporation.
In the mathematics of structural rigidity, a rigidity matroid is a matroid that describes the number of degrees of freedom of an undirected graph with rigid edges of fixed lengths, embedded into Euclidean space. In a rigidity matroid for a graph with n vertices in d-dimensional space, a set of edges that defines a subgraph with k degrees of freedom has matroid rank dn − k. A set of edges is independent if and only if, for every edge in the set, removing the edge would increase the number of degrees of freedom of the remaining subgraph.
In mathematics, a partition matroid or partitional matroid is a matroid that is a direct sum of uniform matroids. It is defined over a base set in which the elements are partitioned into different categories. For each category, there is a capacity constraint - a maximum number of allowed elements from this category. The independent sets of a partition matroid are exactly the sets in which, for each category, the number of elements from this category is at most the category capacity.
In graph theory, a branch of mathematics, the Erdős–Hajnal conjecture states that families of graphs defined by forbidden induced subgraphs have either large cliques or large independent sets. It is named for Paul Erdős and András Hajnal.
In extremal graph theory, the even circuit theorem is a result of Paul Erdős according to which an n-vertex graph that does not have a simple cycle of length 2k can only have O(n1 + 1/k) edges. For instance, 4-cycle-free graphs have O(n3/2) edges, 6-cycle-free graphs have O(n4/3) edges, etc.
In combinatorial optimization, the matroid parity problem is a problem of finding the largest independent set of paired elements in a matroid. The problem was formulated by Lawler (1976) as a common generalization of graph matching and matroid intersection. It is also known as polymatroid matching, or the matchoid problem.
A sparsity matroid is a mathematical structure that captures how densely a multigraph is populated with edges. To unpack this a little, sparsity is a measure of density of a graph that bounds the number of edges in any subgraph. The property of having a particular matroid as its density measure is invariant under graph isomorphisms and so it is a graph invariant.
