valency


In a graph, multigraphMathworldPlanetmath, or pseudographMathworldPlanetmath G, the valencyPlanetmathPlanetmath 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 graphsMathworldPlanetmath, in- and out- are prefixed to any of the synonyms, to count incoming and outgoing edges separately.

If ρ(v) is used for the valency of vertex v, the notation ρ(G) (or ρ on its own if there is no scope for confusion) denotes the maximum valency found in graph G. Another notation often seen is δ(G) and Δ(G) for lowest and highest valency in G respectively.

If the valency is the same number (ρ, say) for all its vertices, G is called regular. More specifically it is called ρ-valent or ρ-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 ρ3 these structures start getting more interesting. 3-valent (or trivalent) graphs are also known as cubic graphs.

A ρ-valent graph with n vertices has nρ/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 ρ-valent
Defines trivalent graph
Defines cubic graph
Defines regular
Defines regular graph