We say that is a subgraph of if and . In this case we write .
If contains all edges of that join two vertices in then is said to be the subgraph induced or spanned by and is denoted by . Thus, a subgraph of is an induced subgraph if . If , then is said to be a spanning subgraph of .
Often, new graphs are constructed from old ones by deleting or adding some vertices and edges. If , then is the subgraph of obtained by deleting the vertices in and all edges incident with them. Similarly, if , then . If and , then this notation is simplified to and . Similarly, if and are nonadjacent vertices of , then is obtained from by joining to .
Adapted with permission of the author from by Béla Bollobás, published by Springer-Verlag New York, Inc., 1998.
|Date of creation||2013-03-22 12:30:59|
|Last modified on||2013-03-22 12:30:59|
|Last modified by||CWoo (3771)|