Girth

From Wikipedia, the free encyclopedia

A girth is also a piece of equipment used to hold the saddle on a horse.

Girth is the circumference of a cylindrical object.

Girth is sometimes used by postal services and delivery companies as basis for pricing. For example Canada Post require that item's length plus girth do not exceeds a maximum allowed value. The girth in this case is 2 * (height + width). Girth is the measurement you get when you wrap a tape measure all the way around the box (its two smallest dimensions).

In graph theory, the girth of a graph is the length of the shortest cycle contained in the graph.^[1] If the graph does not contain any cycles, its girth is defined to be infinity. For example, a 4-cycle (square) has girth 4. A grid has girth 4 as well, and a triangular mesh has girth 3. A cubic graph of girth <math>g</math> that is as small as possible is known as a <math>g</math>-cage. The Petersen graph is the unique 5-cage (it is the smallest cubic graph of girth 5), the Heawood graph is the unique 6-cage, and the Tutte eight cage is the unique 8-cage.^[2] A graph with girth ≥ 4 is triangle-free.

Petersen graph blue.svg

The Petersen graph, of girth 5

Heawood graph.svg

The Heawood graph, of girth 6

Tutte eight cage.svg

The Tutte eight cage, of girth 8

[edit] References

^ R. Diestel, Graph Theory, p.8. 3rd Edition, Springer-Verlag, 2005
^ Brouwer, Andreas E., Cages, <http://www.win.tue.nl/~aeb/drg/graphs/>. Electronic supplement to the book Distance-Regular Graphs (Brouwer, Cohen, and Neumaier 1989, Springer-Verlag).