WikiMili The Free Encyclopedia

In graph theory, an **induced subgraph** of a graph is another graph, formed from a subset of the vertices of the graph and all of the edges connecting pairs of vertices in that subset.

In mathematics, **graph theory** is the study of *graphs*, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of *vertices* which are connected by *edges*. A distinction is made between **undirected graphs**, where edges link two vertices symmetrically, and **directed graphs**, where edges, then called *arrows*, link two vertices asymmetrically; see Graph for more detailed definitions and for other variations in the types of graph that are commonly considered. Graphs are one of the prime objects of study in discrete mathematics.

In mathematics, a set *A* is a **subset** of a set *B*, or equivalently *B* is a **superset** of *A*, if *A* is "contained" inside *B*, that is, all elements of *A* are also elements of *B*. *A* and *B* may coincide. The relationship of one set being a subset of another is called **inclusion** or sometimes **containment**. *A* is a subset of *B* may also be expressed as *B* includes *A*; or *A* is included in *B*.

Formally, let *G* = (*V*, *E*) be any graph, and let *S* ⊂ *V* be any subset of vertices of G. Then the induced subgraph *G*[*S*] is the graph whose vertex set is S and whose edge set consists of all of the edges in E that have both endpoints in S.^{ [1] } The same definition works for undirected graphs, directed graphs, and even multigraphs.

In mathematics, and more specifically in graph theory, a **directed graph** is a graph that is made up of a set of vertices connected by edges, where the edges have a direction associated with them.

In mathematics, and more specifically in graph theory, a **multigraph** is a graph which is permitted to have multiple edges, that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge.

The induced subgraph *G*[*S*] may also be called the subgraph induced in G by S, or (if context makes the choice of G unambiguous) the induced subgraph of S.

Important types of induced subgraphs include the following.

- Induced paths are induced subgraphs that are paths. The shortest path between any two vertices in an unweighted graph is always an induced path, because any additional edges between pairs of vertices that could cause it to be not induced would also cause it to be not shortest. Conversely, in distance-hereditary graphs, every induced path is a shortest path.
^{ [2] } - Induced cycles are induced subgraphs or cycles. The girth of a graph is defined by the length of its shortest cycle, which is always an induced cycle. According to the strong perfect graph theorem, induced cycles and their complements play a critical role in the characterization of perfect graphs.
^{ [3] } - Cliques and independent sets are induced subgraphs that are respectively complete graphs or edgeless graphs.
- The neighborhood of a vertex is the induced subgraph of all vertices adjacent to it.

In the mathematical area of graph theory, an **induced path** in an undirected graph *G* is a path that is an induced subgraph of *G*. That is, it is a sequence of vertices in *G* such that each two adjacent vertices in the sequence are connected by an edge in *G*, and each two nonadjacent vertices in the sequence are not connected by any edge in *G*. An induced path is sometimes called a **snake**, and the problem of finding long induced paths in hypercube graphs is known as the snake-in-the-box problem.

In graph theory, a **path** in a graph is a finite or infinite sequence of edges which connect a sequence of vertices which, by most definitions, are all distinct from one another. In a directed graph, a **directed path** is again a sequence of edges which connect a sequence of vertices, but with the added restriction that the edges all be directed in the same direction.

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.

The induced subgraph isomorphism problem is a form of the subgraph isomorphism problem in which the goal is to test whether one graph can be found as an induced subgraph of another. Because it includes the clique problem as a special case, it is NP-complete.^{ [4] }

In complexity theory and graph theory, **induced subgraph isomorphism** is an NP-complete decision problem that involves finding a given graph as an induced subgraph of a larger graph.

In theoretical computer science, the **subgraph isomorphism** problem is a computational task in which two graphs *G* and *H* are given as input, and one must determine whether *G* contains a subgraph that is isomorphic to *H*. Subgraph isomorphism is a generalization of both the maximum clique problem and the problem of testing whether a graph contains a Hamiltonian cycle, and is therefore NP-complete. However certain other cases of subgraph isomorphism may be solved in polynomial time.

In computer science, the **clique problem** is the computational problem of finding cliques in a graph. It has several different formulations depending on which cliques, and what information about the cliques, should be found. Common formulations of the clique problem include finding a maximum clique, finding a maximum weight clique in a weighted graph, listing all maximal cliques, and solving the decision problem of testing whether a graph contains a clique larger than a given size.

This is a **glossary of graph theory terms**. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by edges.

In graph theory, a **perfect graph** is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph. Due to the strong perfect graph theorem, perfect graphs are the same as **Berge graphs**. A graph G is a Berge graph if neither G nor its complement contains an induced cycle of odd length 5 or more.

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*. The name line graph comes from a paper by Harary & Norman (1960) although both Whitney (1932) and Krausz (1943) used the construction before this. Other terms used for the line graph include the **covering graph**, the **derivative**, the **edge-to-vertex dual**, the **conjugate**, the **representative graph**, and the **ϑ-obrazom**, as well as the **edge graph**, the **interchange graph**, the **adjoint graph**, and the **derived graph**.

In the mathematical area of graph theory, a **chordal graph** is one in which all cycles of four or more vertices have a *chord*, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called **rigid circuit graphs** or **triangulated graphs**.

In graph theory, the **strong perfect graph theorem** is a forbidden graph characterization of the perfect graphs as being exactly the graphs that have neither odd holes nor odd antiholes. It was conjectured by Claude Berge in 1961. A proof by Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas was announced in 2002 and published by them in 2006.

In graph theory, a **cograph**, or **complement-reducible graph**, or ** P_{4}-free graph**, is a graph that can be generated from the single-vertex graph

In the mathematical discipline of graph theory the **Tutte theorem**, named after William Thomas Tutte, is a characterization of graphs with perfect matchings. It is a generalization of Hall's marriage theorem from bipartite to arbitrary graphs. It is a special case of the Tutte–Berge formula.

In the mathematical area of graph theory, **Kőnig's theorem**, proved by Dénes Kőnig (1931), 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 subgraph of *n* − 1 vertices has a perfect matching.

In graph theory, a branch of mathematics, a **split graph** is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by Földes and Hammer, and independently introduced by Tyshkevich and Chernyak (1979).

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 of the graph 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 graph theory, a **trivially perfect graph** is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals the number of maximal cliques. Trivially perfect graphs were first studied by but were named by Golumbic (1978); Golumbic writes that "the name was chosen since it is trivial to show that such a graph is perfect." Trivially perfect graphs are also known as **comparability graphs of trees**, **arborescent comparability graphs**, and **quasi-threshold graphs**.

In the mathematical area of graph theory, an undirected graph *G* is **strongly chordal** if it is a chordal graph and every cycle of even length in *G* has an *odd chord*, i.e., an edge that connects two vertices that are an odd distance (>1) apart from each other in the cycle.

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, a **skew partition** of a graph is a partition of its vertices into two subsets, such that the induced subgraph formed by one of the two subsets is disconnected and the induced subgraph formed by the other subset is the complement of a disconnected graph. Skew partitions play an important role in the theory of perfect graphs.

In graph theory, a **Ptolemaic graph** is an undirected graph whose shortest path distances obey Ptolemy's inequality, which in turn was named after the Greek astronomer and mathematician Ptolemy. The Ptolemaic graphs are exactly the graphs that are both chordal and distance-hereditary; they include the block graphs and are a subclass of the perfect graphs.

- ↑ Diestel, Reinhard (2006),
*Graph Theory*, Graduate texts in mathematics,**173**, Springer-Verlag, pp. 3–4, ISBN 9783540261834 . - ↑ Howorka, Edward (1977), "A characterization of distance-hereditary graphs",
*The Quarterly Journal of Mathematics. Oxford. Second Series*,**28**(112): 417–420, doi:10.1093/qmath/28.4.417, MR 0485544 . - ↑ Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006), "The strong perfect graph theorem",
*Annals of Mathematics*,**164**(1): 51–229, arXiv: math/0212070, doi:10.4007/annals.2006.164.51, MR 2233847 . - ↑ Johnson, David S. (1985), "The NP-completeness column: an ongoing guide",
*Journal of Algorithms*,**6**(3): 434–451, doi:10.1016/0196-6774(85)90012-4, MR 0800733 .

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.