subgraph
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.
Title | subgraph |
Canonical name | Subgraph |
Date of creation | 2013-03-22 12:30:59 |
Last modified on | 2013-03-22 12:30:59 |
Owner | CWoo (3771) |
Last modified by | CWoo (3771) |
Numerical id | 10 |
Author | CWoo (3771) |
Entry type | Definition |
Classification | msc 05C99 |
Related topic | Graph |
Related topic | Pseudograph |
Related topic | Multigraph |
Defines | induced |
Defines | spanned by |
Defines | spanning |
Defines | spanning subgraph |
Defines | induced subgraph |