Long cycles

From InterSciWiki
Jump to: navigation, search

The Theory of Long Cycles

(c) Douglas R. White

Consider a network composes of n nodes and m edges (i.e., symmetric ties, this might consider directed arcs to be edges as well).

A set of node independent cycles is one in which every ordered pair of cycles has at least one edge that is not contained in the other.

The cycle rank of a network is its maximal number of node independent cycles. A set of node independent cycles that satisfied the cycle rank of a network is a cycle basis.

Theorem (well known). The cycle rank of a connected network is k = m - n + 1, the number of chords of its minimal spanning tree.

Conjecture (probably wrong): The k = m - n + 1 longest chordless cycles of a graph are a cycle basis of the network.

Problem: A spanning tree of a network with the greatest number of edges is a cycle basis where chords connecting nodes with degree 1 form the longest chordless cycles. This does us no good in proving the conjecture since all spanning trees will have n - 1 edges.

So the conjecture must depend on the structure of the requisite spanning tree.

LongCycles.png

On the length of longest chordless cycles 4OR: A Quarterly Journal of Operations Research. Issue Volume 3, Number 2: 1614-2411 / June, 2005


Generating cycle spaces for graphs on surfaces with small genera European Journal of Combinatorics. Volume 25, Issue 7, October 2004, Pages 1087-1105