TOPICS
Search

Chordless Graph


A chordless graph is a simple graph possessing no chords.

A chordal graph (which possesses no chordless cycles) is not the same as (or converse of) a chordless graph (which possesses no chords). For example, the square graph C_4 is chordless but not chordal, the diamond graph and tetrahedral graph K_4 are chordal but not chordless, and empty graphs K^__n, path graphs P_n, and the triangle graph C_3 are both chordal and chordless.

ChordlessConnected

The numbers of connected simple chordless graphs on n=1, 2, ... nodes are 1, 1, 2, 4, 10, 27, ... (OEIS A287693), the first few of which are illustrated above.

Chordless

The numbers of not-necessarily connected simple chordless graphs on n=1, 2, ... nodes are 1, 2, 4, 9, 21, 56, ... (OEIS A287694), the first few of which are illustrated above.


See also

Chordal Graph, Chordless Cycle, Cycle Chord

Explore with Wolfram|Alpha

References

Sloane, N. J. A. Sequences A287693 and A287694 in "The On-Line Encyclopedia of Integer Sequences."

Cite this as:

Weisstein, Eric W. "Chordless Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ChordlessGraph.html

Subject classifications