ENCYCLOPEDIA 4U .com



Encyclopedia Home Page

Google
  Web Encyclopedia4u.com

 

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




Content on this web site is provided for informational purposes only. We accept no responsibility for any loss, injury or inconvenience sustained by any person resulting from information published on this site. We encourage you to verify any critical information with the relevant authorities.



Copyright © 2005 Par Web Solutions All Rights reserved.
| Privacy

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Girth".