| Version 2 |
Version 1 |
| \PMlinkescapeword{cyclic} |
\PMlinkescapeword{cyclic} |
| \PMlinkescapeword{scope} |
|
| \PMlinkescapeword{structures} |
\PMlinkescapeword{structures} |
|
|
| In a graph, multigraph, or pseudograph $G$, the {\bf valency} of a vertex is |
In a graph, multigraph, or pseudograph $G$, the {\bf valency} of a vertex is |
| the number of edges attached to it (note that a loop counts twice). |
the number of edges attached to it (note that a loop counts twice). |
|
|
| Synonymous with {\bf \PMlinkescapetext{valence}} and |
Synonymous with {\bf \PMlinkescapetext{valence}} and |
| {\bf \PMlinkescapetext{degree}}. There are some unrelated things also |
{\bf \PMlinkescapetext{degree}}. There are some unrelated things also |
| called valence; there are of course many things all called degree. |
called {\em valence\/}; there are of course many unrelated things all |
|
called {\em degree\/}. |
|
|
| For directed graphs, {\bf in-} and {\bf out-} are prefixed to any of the synonyms, to count incoming and outgoing edges separately. |
For directed graphs, {\bf in-} and {\bf out-} are prefixed to any of the synonyms, to count incoming and outgoing edges separately. |
|
|
| If $\rho(\hbox{\sc v})$ is used for the valency of vertex $\hbox{\sc v}$, the notation $\rho(G)$ (or $\rho$ on its own if there is no scope for confusion) denotes the maximum valency found in graph $G$. Another notation often seen is $\delta(G)$ and $\Delta(G)$ for lowest and highest valency in $G$ respectively. |
The lowest and highest valency in $G$ are sometimes called $\delta(G)$ and $\Delta(G)$ respectively. If the valency is the same for all its vertices, $G$ |
|
is called {\bf regular}. More specifically it is called {\bf $\delta$-valent}; connected (components of) |
| If the valency is the same number ($\rho$, say) for all its vertices, $G$ is called {\bf regular}. More specifically it is called {\bf $\rho$-valent} or $\rho$-regular. Connected (components of)\dots |
|
| % |
% |
| \begin{itemize} |
\begin{itemize} |
|
|
| \item \dots0-valent graphs are edgeless vertices, |
\item \dots0-valent graphs are edgeless vertices, |
|
|
| \item \dots1-valent graphs are pairs of vertices joined by an edge, |
\item \dots1-valent graphs are pairs of vertices joined by an edge, |
|
|
| \item \dots2-valent graphs are cyclic graphs, i.e.\ $n$-gons, of various sizes |
\item \dots2-valent graphs are cyclic graphs, i.e.\ $n$-gons, of various sizes |
|
|
|
\item From $\rho\ge3$ these structures start getting more interesting.
|
\item From $\delta\ge3$ the structures start getting interesting.
|
| 3-valent (or {\bf trivalent}) graphs are also known as |
3-valent (or {\bf trivalent}) graphs are also known as |
| {\bf cubic graphs}. |
{\bf cubic graphs}. |
|
|
| \end{itemize} |
\end{itemize} |
|
|
|
A $\rho$-valent graph with $n$ vertices has $n\,\rho/2$ edges.
|
A $\delta$-valent graph with $n$ vertices has $n\,\delta/2$ edges.
|
