Requiring chords in cycles

详细信息    查看全文

• 作者：Terry A. McKee
• 关键词：Chord ; Chordal graph ; Chordal bipartite graph ; Distance-hereditary graph ; Strongly chordal graph
• 刊名：Discrete Mathematics
• 出版年：2005
• 出版时间：2005
• 年：2005
• 卷：297
• 期：1-3
• 页码：182-189
• 全文大小：169 K

文摘

Jamison proved that every cycle of length greater than three in a graph has a chord—in other words, the graph is chordal—if and only if every k-cycle is the sum of e31f339b8aad29d6e99c34958df8"" title=""Click to view the MathML source"">k-2 triangles. This result generalizes to having or not having crossing chords and to having strong chords, with similar characterizations of a variety of graph classes that includes chordal bipartite, distance-hereditary, and strongly chordal graphs.