Girth of a graph

From Graph
(Redirected from Girth)
Jump to: navigation, search

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