The Hamiltonian path problem is a topic discussed in the fields of complexity theory and graph theory. It decides if a directed or undirected graph, G, contains a Hamiltonian path, a path that visits every vertex in the graph exactly once. The problem may specify the start and end of the path, in which case the starting vertex s and ending vertex t must be identified.
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets and , that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.
In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.
In the mathematical area of graph theory, a clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph is an induced subgraph of that is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied.
In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set of vertices such that for every two vertices in , there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in . A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening.
In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.
In graph theory, the perfect graph theorem of László Lovász states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by Berge, and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem characterizing perfect graphs by their forbidden induced subgraphs.
In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. L(G) is constructed in the following way: for each edge in G, make a vertex in L(G); for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L(G).
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 field of graph theory, a quartic graph is a graph where all vertices have degree 4. In other words, a quartic graph is a 4-regular graph.
In graph theory, the Grundy number or Grundy chromatic number of an undirected graph is the maximum number of colors that can be used by a greedy coloring strategy that considers the vertices of the graph in sequence and assigns each vertex its first available color, using a vertex ordering chosen to use as many colors as possible. Grundy numbers are named after P. M. Grundy, who studied an analogous concept for directed graphs in 1939. The undirected version was introduced by Christen & Selkow (1979).
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, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph.
In graph theory, a branch of discrete mathematics, a distance-hereditary graph is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any induced subgraph inherits the distances of the larger graph.
In graph theory, a branch of combinatorial mathematics, a block graph or clique tree is a type of undirected graph in which every biconnected component (block) is a clique.
In graph theory and computer science, a dense subgraph is a subgraph with many edges per vertex. This is formalized as follows: let G = (V, E) be an undirected graph and let S = (VS, ES) be a subgraph of G. Then the density of S is defined to be:
In graph theory, a well-covered graph is an undirected graph in which the minimal vertex covers all have the same size. Here, a vertex cover is a set of vertices that touches all edges, and it is minimal if removing any vertex from it would leave some edge uncovered. Equivalently, well-covered graphs are the graphs in which all maximal independent sets have equal size. Well-covered graphs were defined and first studied by Michael D. Plummer in 1970.
In the mathematical discipline of graph theory, Petersen's theorem, named after Julius Petersen, is one of the earliest results in graph theory and can be stated as follows:
Petersen's Theorem. Every cubic, bridgeless graph contains a perfect matching.
In graph theory, a branch of mathematics, the kth powerGk of an undirected graph G is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in G is at most k. Powers of graphs are referred to using terminology similar to that of exponentiation of numbers: G2 is called the square of G, G3 is called the cube of G, etc.
In graph theory, the matching polytope of a given graph is a geometric object representing the possible matchings in the graph. It is a convex polytope each of whose corners corresponds to a matching. It has great theoretical importance in the theory of matching.
