valency

In a graph, multigraph, or pseudograph $G$, the valency of a vertex is the number of edges attached to it (note that a loop counts twice).

Synonymous with and . There are some unrelated things also called valence; there are of course many things all called degree.

For directed graphs, in- and out- are prefixed to any of the synonyms, to count incoming and outgoing edges separately.

If $\rho (\mathrm{\text{v}})$ is used for the valency of vertex 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 $\mathrm{\Delta }(G)$ for lowest and highest valency in $G$ respectively.

If the valency is the same number ($\rho$, say) for all its vertices, $G$ is called regular. More specifically it is called $\rho$-valent or $\rho$-regular. Connected (components of)…

• …0-valent graphs are edgeless vertices,

• …1-valent graphs are pairs of vertices joined by an edge,

• …2-valent graphs are cyclic graphs, i.e. $n$-gons, of various sizes

• From $\rho ⩾3$ these structures start getting more interesting. 3-valent (or trivalent) graphs are also known as cubic graphs.

A $\rho$-valent graph with $n$ vertices has $n\rho /2$ edges.

Title	valency
Canonical name	Valency
Date of creation	2013-03-22 15:10:17
Last modified on	2013-03-22 15:10:17
Owner	marijke (8873)
Last modified by	marijke (8873)
Numerical id	6
Author	marijke (8873)
Entry type	Definition
Classification	msc 05C40
Synonym	valence
Synonym	degree
Defines	$\rho$-valent
Defines	trivalent graph
Defines	cubic graph
Defines	regular
Defines	regular graph