Induced subgraph

From Encyclopedia of Mathematics
Jump to: navigation, search

of a graph $G $

The graph $G[S]$ having as vertex set a given subset $S$ of the vertex set of $G$ and as edges between $x,y \in S$ all edges that exist between $x,y$ in $G$. If $G$ has an incidence matrix $I$, then the incidence matrix $I[S]$ consists precisely of those rows of $I$ corresponding to vertices in $S$.

How to Cite This Entry:
Induced subgraph. Encyclopedia of Mathematics. URL: