TOPICS
Search

Cycle Chord


CycleChord

A chord of a graph cycle C is an edge not in the edge set of C whose endpoints lie in the vertex set C (West 2000, p. 225). For example, in the diamond graph as labeled above, the edge (3,4) is a chord of the cycle (1,3,2,4,1).

The motivation for the term "chord" is geometric. In particular, if a cycle is drawn with its vertices lying on the a circle and its chords are drawn as line segments, then the chords of the cycle are chords of the circle (West 2000, p. 225).

Graph bridges are not chords since they do not lie on a cycle. Similarly, in order to lie on a cycle, both endpoints of a chord must be of vertex degree at least 3.

A graph cycle possessing no chord (sometimes with the added restriction that the cycle be of length four or greater; e.g., West 2000, p. 225), is said to be a chordless cycle. Chordless cycles are important in the study and characterization of perfect graphs.

A graph in which every graph cycle possesses a chord (i.e., in which no chordless cycles of length four or greater exist) is said to be a chordal graph. Similarly, a graph in which no chords exist is said to be a chordless graph.


See also

Chord, Chordal Graph, Chordless Cycle, Chordless Graph, Graph Cycle, Meyniel Graph

Explore with Wolfram|Alpha

References

West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, p. 225, 2000.

Referenced on Wolfram|Alpha

Cycle Chord

Cite this as:

Weisstein, Eric W. "Cycle Chord." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/CycleChord.html

Subject classifications