Encyclopedia > Girth

  Article Content

Girth

In graph theory, the girth of a graph is the length of the shortest cycle contained in the graph. If the graph doesn't 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.

The Heawood graph in the figure on the left is the smallest trivalent graph with girth 6; the Petersen graph on the right is the smallest trivalent graph with girth 5.


In common usage, girth refers to the circumference of a cylindrical object such as a tree trunk



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Psychology

... inquiry present in other sciences. Whether psychology can follow the model of the natural sciences, however, is still yet to be fully tested. While some fields ...