Induced subgraph

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.

DefinitionEdit

Formally, let   be any graph, and let   be any subset of vertices of G. Then the induced subgraph   is the graph whose vertex set is   and whose edge set consists of all of the edges in   that have both endpoints in  .[1] That is, for any two vertices  ,   and   are adjacent in   if and of if they are adjacent in  . The same definition works for undirected graphs, directed graphs, and even multigraphs.

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

ExamplesEdit

Important types of induced subgraphs include the following.

 
The snake-in-the-box problem concerns the longest induced paths in hypercube graphs

ComputationEdit

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]

ReferencesEdit

  1. ^ Diestel, Reinhard (2006), Graph Theory, Graduate texts in mathematics, 173, Springer-Verlag, pp. 3–4, ISBN 9783540261834.
  2. ^ Howorka, Edward (1977), "A characterization of distance-hereditary graphs", The Quarterly Journal of Mathematics, Second Series, 28 (112): 417–420, doi:10.1093/qmath/28.4.417, MR 0485544.
  3. ^ 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.
  4. ^ 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.