Definitions
A peripheral cycle in a graph can be defined formally in one of several equivalent ways:
- is peripheral if it is a simple cycle in a connected graph with the property that, for every two edges and in, there exists a path in that starts with, ends with, and has no interior vertices belonging to .
- is peripheral if it is an induced cycle with the property that the subgraph formed by deleting the edges and vertices of is connected.
- If is any subgraph of, a bridge of is a minimal subgraph of that is edge-disjoint from and that has the property that all of its points of attachments (vertices adjacent to edges in both and ) belong to . A simple cycle is peripheral if it has exactly one bridge.
The equivalence of these definitions is not hard to see: a connected subgraph of (together with the edges linking it to ), or a chord of a cycle that causes it to fail to be induced, must in either case be a bridge, and must also be an equivalence class of the binary relation on edges in which two edges are related if they are the ends of a path with no interior vertices in .
Read more about this topic: Peripheral Cycle
Famous quotes containing the word definitions:
“What I do not like about our definitions of genius is that there is in them nothing of the day of judgment, nothing of resounding through eternity and nothing of the footsteps of the Almighty.”
—G.C. (Georg Christoph)
“The loosening, for some people, of rigid role definitions for men and women has shown that dads can be great at calming babies—if they take the time and make the effort to learn how. It’s that time and effort that not only teaches the dad how to calm the babies, but also turns him into a parent, just as the time and effort the mother puts into the babies turns her into a parent.”
—Pamela Patrick Novotny (20th century)