Related Research Articles
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.
This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.
In the mathematical field of graph theory, a spanning treeT of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree. If all of the edges of G are also edges of a spanning tree T of G, then G is a tree and is identical to T.
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 the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. In other words, a subset of the edges is a matching if each vertex appears in at most one edge of that matching. Finding a matching in a bipartite graph can be treated as a network flow problem.
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 graph theory, a branch of mathematics, the circuit rank, cyclomatic number, cycle rank, or nullity of an undirected graph is the minimum number of edges that must be removed from the graph to break all its cycles, making it into a tree or forest. It is equal to the number of independent cycles in the graph. Unlike the corresponding feedback arc set problem for directed graphs, the circuit rank r is easily computed using the formula
In graph theory, the Dulmage–Mendelsohn decomposition is a partition of the vertices of a bipartite graph into subsets, with the property that two adjacent vertices belong to the same subset if and only if they are paired with each other in a perfect matching of the graph. It is named after A. L. Dulmage and Nathan Mendelsohn, who published it in 1958. A generalization to any graph is the Edmonds–Gallai decomposition, using the Blossom algorithm.
In graph theory, a connected graph is k-edge-connected if it remains connected whenever fewer than k edges are removed.
In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig, describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.
In graph theory, a mathematical discipline, a factor-critical graph is a graph with n vertices in which every induced 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 clique cover or partition into cliques of a given undirected graph is a partition of the vertices into cliques, subsets of vertices within which every two vertices are adjacent. A minimum clique cover is a clique cover that uses as few cliques as possible. The minimum k for which a clique cover exists is called the clique cover number of the given graph.
In the mathematical field of graph theory, a graph G is said to be hypohamiltonian if G itself does not have a Hamiltonian cycle but every graph formed by removing a single vertex from G is Hamiltonian.
In computer science, iterative compression is an algorithmic technique for the design of fixed-parameter tractable algorithms, in which one element is added to the problem in each step, and a small solution for the problem prior to the addition is used to help find a small solution to the problem after the step.
In graph theory, a matching in a hypergraph is a set of hyperedges, in which every two hyperedges are disjoint. It is an extension of the notion of matching in a graph.
In graph theory, a balanced hypergraph is a hypergraph that has several properties analogous to that of a bipartite graph.
References
- ↑ Brigham, Robert C.; Harary, Frank; Violin, Elizabeth C.; Yellen, Jay (2005), "Perfect-matching preclusion", Congressus Numerantium, 174, Utilitas Mathematica Publishing, Inc.: 185–192.
- 1 2 Cheng, Eddie; Lipták, László (2007), "Matching preclusion for some interconnection networks", Networks, 50 (2): 173–180, doi: 10.1002/net.20187 .
- ↑ Cheng, Eddie; Lesniak, Linda; Lipman, Marc J.; Lipták, László (2009), "Conditional matching preclusion sets", Information Sciences, 179 (8): 1092–1101, doi:10.1016/j.ins.2008.10.029 .
- ↑ Park, Jung-Heum; Son, Sang Hyuk (2009), "Conditional matching preclusion for hypercube-like interconnection networks", Theoretical Computer Science, 410 (27–29): 2632–2640, doi: 10.1016/j.tcs.2009.02.041 .
- ↑ Lacroix, Mathieu; Ridha Mahjoub, A.; Martin, Sébastien; Picouleau, Christophe (March 2012). "On the NP-completeness of the perfect matching free subgraph problem". Theoretical Computer Science. 423: 25–29. doi:10.1016/j.tcs.2011.12.065.
- ↑ Dourado, Mitre Costa; Meierling, Dirk; Penso, Lucia D.; Rautenbach, Dieter; Protti, Fabio; de Almeida, Aline Ribeiro (2015), "Robust recoverable perfect matchings", Networks, 66 (3): 210–213, doi:10.1002/net.21624 .
- ↑ Mao, Yaping; Wang, Zhao; Cheng, Eddie; Melekian, Christopher (2018), "Strong matching preclusion number of graphs", Theoretical Computer Science, 713: 11–20, doi: 10.1016/j.tcs.2017.12.035 .
 | This graph theory-related article is a stub. You can help Wikipedia by expanding it. |