Cycle Chord

 

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

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.

---

REFERENCES

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

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength