|
|
|
Viewing Version
6
of
'subgraph'
|
[ view 'subgraph'
|
back to history
]
| Title of object: |
subgraph |
| Canonical Name: |
Subgraph |
| Type: |
Definition |
| Created on: |
2002-03-06 23:50:50 |
| Modified on: |
2004-01-25 00:58:31 |
| Classification: |
msc:05C99 |
| Keywords: |
graph |
| Defines: |
induced, spanned by, spanning, spanning subgraph, induced subgraph |
Revision comment (for changes between this and next version):
| Changes for correction #13056 ('linking policy'). |
Preamble:
% this is the default PlanetMath preamble. as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.
% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
% there are many more packages, add them here as you need them
% define commands here |
Content:
We say that $G' = (V',E')$ is a \emph{subgraph} of $G = (V,E)$ if $V' \subseteq V$ and $E' \subseteq E$. In this case we write $G' \subseteq G$.
If $G'$ contains \emph{all edges} of $G$ that join two vertices in $V'$ then $G'$ is said to be the subgraph \emph{induced} or \emph{spanned by} $V'$ and is denoted by $G[V']$. Thus, a subgraph $G'$ of $G$ is an induced subgraph if $G' = G[V(G')]$. If $V' = V$, then $G'$ is said to be a \emph{spanning} subgraph of $G$.
Often, new graphs are constructed from old ones by deleting or adding some vertices and edges. If $W \subset V(G)$, then $G - W = G[V\setminus W]$ is the subgraph of $G$ obtained by deleting the vertices in $W$ \emph{and all edges incident with them}. Similarly, if $E' \subseteq E(G)$, then $G - E' = (V(G),E(G) \setminus E')$. If $W = {w}$ and $E' = {xy}$, then this notation is simplified to $G - w$ and $G - xy$. Similarly, if $x$ and $y$ are nonadjacent vertices of $G$, then $G + xy$ is obtained from $G$ by joining $x$ to $y$.
\footnotesize{Adapted with permission of the author from \emph{\PMlinkescapetext{Modern Graph Theory}} by B\'{e}la Bollob\'{a}s, published by Springer-Verlag New York, Inc., 1998.} |
|
|
|
|
|
