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
1 E6 W

... W To help compare different orders of magnitude we list here powers between 106 watts and 107 watts. See also powers of other orders of magnitude. Weaker powers ...