Jump to content

Peripheral cycle

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Chris-martin (talk | contribs) at 04:13, 30 November 2008 (remove dead external link). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In graph theory, a peripheral cycle in a graph G is a cycle that is induced and non-separating. That is, it is a cycle C such that

  • no two vertices in C are connected by an edge not in C and
  • the graph G − C (we are deleting vertices of C and all incident edges) is connected.

Properties

In a 3-connected planar graph, boundaries of faces are precisely the peripheral cycles.

The cycle space of a 3-connected graph is generated by the peripheral cycles (a result of Tutte, 1963).

Retrieved from "https://en.wikipedia.org/w/index.php?title=Peripheral_cycle&oldid=254927220"