Girth of a graph: Difference between revisions
(Created page with "{{undirected graph numerical invariant}} ==Definition== Suppose <math>G</math> is an undirected graph. The '''girth''' of <math>G</math> is defined as the minimum possib...") |
No edit summary |
||
| Line 4: | Line 4: | ||
Suppose <math>G</math> is an [[undirected graph]]. The '''girth''' of <math>G</math> is defined as the minimum possible length of a cycle of length 3 or more (i.e., a [[subgraph]] isomorphic to a [[cycle graph]]) in <math>G</math>. | Suppose <math>G</math> is an [[undirected graph]]. The '''girth''' of <math>G</math> is defined as the minimum possible length of a cycle of length 3 or more (i.e., a [[subgraph]] isomorphic to a [[cycle graph]]) in <math>G</math>. | ||
==Related invariants== | |||
* [[Even girth]] refers to the minimum among the lengths of all cycles of even length. | |||
* [[Odd girth]] refers to the minimum among the lengths of all cycles of odd length. | |||
The girth of a graph is the minimum of its even girth and odd girth. | |||
==Related graph properties== | ==Related graph properties== | ||
Latest revision as of 02:39, 29 May 2012
Template:Undirected graph numerical invariant
Definition
Suppose is an undirected graph. The girth of is defined as the minimum possible length of a cycle of length 3 or more (i.e., a subgraph isomorphic to a cycle graph) in .
Related invariants
- Even girth refers to the minimum among the lengths of all cycles of even length.
- Odd girth refers to the minimum among the lengths of all cycles of odd length.
The girth of a graph is the minimum of its even girth and odd girth.
Related graph properties
- Forest and tree: Note that the girth of a graph is if and only if the graph is a forest. For a connected graph, the girth is if and only if the graph is a tree.
- Triangle-free graph is a graph of girth 4 or more
