Girth

From Wikipedia, the free encyclopedia

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

The girth of an object is a measurement around it. It is sometimes used by postal services and delivery companies as a basis for pricing. For example, Canada Post requires that an item's length plus girth not exceed a maximum allowed value.[1] For a rectangular box, the girth is 2 * (height + width), i.e. the perimeter of a cross section perpendicular to its length.

In graph theory, the girth of a graph is the length of the shortest cycle contained in the graph.[2] 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 g that is as small as possible is known as a g-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.[3] A graph with girth ≥ 4 is triangle-free.

The Petersen graph, of girth 5

The Heawood graph, of girth 6

The Tutte eight cage, of girth 8

[edit] See also

[edit] References

  1. ^ Canada. Canada Post (2008-01-14). Retrieved on 2008-03-13.
  2. ^ R. Diestel, Graph Theory, p.8. 3rd Edition, Springer-Verlag, 2005
  3. ^ 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).