girth


The girth of a graph G is the length of the shortest cycle in G.11There is no widespread agreement on the girth of a forest, which has no cycles. It is also extremely unimportant.

For instance, the girth of any grid d (where d>2) is 4, and the girth of the vertex graph of the dodecahedronMathworldPlanetmathPlanetmath is 5.

Title girth
Canonical name Girth
Date of creation 2013-03-22 12:45:56
Last modified on 2013-03-22 12:45:56
Owner ariels (338)
Last modified by ariels (338)
Numerical id 4
Author ariels (338)
Entry type Definition
Classification msc 05C38
Related topic ChromaticNumberAndGirth