Science Fair Project Encyclopedia
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 Petersen graph is the smallest trivalent graph with girth 5. The Heawood graph is the smallest trivalent graph with girth 6. The Tutte eight cage is the smallest trivalent graph with girth 8.
In common usage, girth refers to the circumference of a cylindrical object such as a tree trunk.
10-26-2009 08:16:03
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details