Circuit rank: Difference between revisions

From Graph
(Created page with "{{undirected graph numerical invariant}} ==Definition== ===Definition for a finite graph=== Suppose <math>G</math> is a finite undirected graph. The ''...")
(No difference)

Revision as of 18:18, 28 May 2012

Template:Undirected graph numerical invariant

Definition

Definition for a finite graph

Suppose is a finite undirected graph. The circuit rank of , also called the cyclotomic number of , is defined in the following equivalent ways:

  1. It is the minimum number of edges that needs to be removed from the edge set of to make it a forest (i.e., an acyclic graph)
  2. It is given by where is the vertex set, is the edge set, and is the number of conncted components of .