Graphs in which every c edges that form a tree are chords of a common cycle

Abstract

Consider the k-connected graphs G in which every edges that form a particular type of induced subgraph must all be chords of a common cycle of G. Extending a few known partial results with and new results exploit the structure of the specified type of induced subgraph, with considerable success when those subgraphs are trees. The common tool behind these new results is a property of k-connectedness from a 2001 paper by Denley and Wu that generalized Dirac’s fundamental 1960 paper on connectivity.

Keywords

• chord
• cycle
• connectivity