# 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:

1. $$V'$$ consists only of vertices from $$V$$, formally $$V'\subseteq V$$.
2. $$E'$$ consists only of edges from $$E$$, formally $$E'\subseteq E$$.
3. $$\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

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!

Github:

### References

#### Bibliography

1. Krumke S. O., Noltemeier H.: "Graphentheoretische Konzepte und Algorithmen", Teubner, 2005, 1st Edition