TOPICS
Search

Cycle Chord


CycleChord

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

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

Graph bridges are not chords since they do not lie on a graph cycle. Similarly, in order to lie on a graph 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 graph 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 of length four or greater possesses a chord 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 Resource. https://mathworld.wolfram.com/CycleChord.html

Subject classifications