In the
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
field of
graph theory
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'' (also called ''nodes'' or ''points'') which are conn ...
, an induced subgraph of a
graph is another graph, formed from a
subset
In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
of the
vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset.
Definition
Formally, let
be any graph, and let
be any subset of vertices of . 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
. That is, for any two vertices
,
and
are adjacent in
if and only if they are adjacent in
. The same definition works for
undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...
s,
directed graph
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pa ...
s, 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
.
Examples
Important types of induced subgraphs include the following.
*
Induced paths are induced subgraphs that are
paths. The
shortest path
In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.
The problem of finding the shortest path between ...
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.
*
Induced cycle
In the mathematical area of graph theory, an induced path in an undirected graph is a path that is an induced subgraph of . That is, it is a sequence of vertices in such that each two adjacent vertices in the sequence are connected by an edge ...
s are induced subgraphs that are
cycles. The
girth
Girth may refer to:
;Mathematics
* Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space
* Girth (geometry), the perimeter of a parallel projection of a shape
* 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.
*
Cliques and
independent sets are induced subgraphs that are respectively
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...
s or
edgeless graph
In the mathematical field of graph theory, the term "null graph" may refer either to the order-zero graph, or alternatively, to any edgeless graph (the latter is sometimes called an "empty graph").
Order-zero graph
The order-zero graph, , is t ...
s.
*
Induced matching In graph theory, an induced matching or strong matching is a subset of the edges of an undirected graph that do not share any vertices (it is a matching) and includes every edge connecting any two vertices in the subset (it is an induced subgraph) ...
s are induced subgraphs that are
matchings.
*The
neighborhood
A neighbourhood (British English, Irish English, Australian English and Canadian English) or neighborhood (American English; see spelling differences) is a geographically localised community within a larger city, town, suburb or rural area, ...
of a vertex is the induced subgraph of all vertices adjacent to it.
Computation
The
induced subgraph isomorphism problem
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.
Problem statement
Formally, the problem takes as input two gra ...
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
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying ...
.
[.]
References
{{reflist
Graph operations
Graph theory objects