Definition: Subdigraphs and Superdigraphs; Induced Subdigraph

Let \(D(V,E,\alpha,\beta)\) be a digraph. A digraph \(S(V',E',\alpha',\beta')\) is called a subdigraph of \(D\), written as \(S\subseteq D\), if it fulfills the following properties:

\(V'\) consists only of vertices from \(V\), formally \(V'\subseteq V\).
\(E'\) consists only of edges from \(E\), formally \(E'\subseteq E\).
\(\alpha'\) and \(\omega'\) are restrictions of \(\alpha\) and \(\omega\) on \(E'\), i.e. \(\alpha':={\alpha|}_{E'}E\mapsto V\) and \(\omega':={\omega|}_{E'}E\mapsto V\).

If \(S\) is a subdigraph of \(D\), then \(D\) is called the superdigraph of \(S\).

If \(S\) contains all the edges \(e\) with \(\alpha(e),\omega(e)\in V'\), then \(S\) is an induced subdigraph of \(D\); we say that the vertices \(V'\) induce or span \(S\) in \(D\) and write \(S:=D[V']\). Thus, if \(V'\subseteq V\) is any set of vertices, \(V'=\{v_1,v_2,\ldots,v_n\}\), then the induced subdigraph \(D[V']=D[v_1,v_2,\ldots,v_n]\) denotes the digraph whose edges are precisely the edges of \(D\) with initial and terminal vertices in \(V'\).

Example

graphs8

In the above figure, the digraphs \(D_2, D_3\) and \(D_4\) are all subdigraphs of the digraph \(D_1\). However, only \(D_2\) and and \(D_4\) are induced subdigraphs of \(D_1\), since

\[D_2=D_1[a,b,c],\quad D_4=D_1[a,c,d],\]

but

\[D_3\neq D_1[c,d].\]

Algorithms: 1
Proofs: 2
Propositions: 3

Thank you to the contributors under CC BY-SA 4.0!