Induced Cycles in Graphs

2014/06/03 by Michael A. Henning, Henning, Michael A., Felix Joos +5
Computer Science · Engineering · #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #VLSI and FPGA Design Techniques #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1406.0606

openalex publication_date 2014/06/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The maximum cardinality of an induced 2-regular subgraph of a graph G is denoted by c_{\rm ind}(G). We prove that if G is an r-regular graph of order n, then c_{\rm ind}(G) ≥ (n)/(2(r-1)) + (1)/((r-1)(r-2)) and we prove that if G is a cubic claw-free graph on order n, then c_{\rm ind}(G) > 13n/20 and this bound is asymptotically best possible.

Related

• Large nearly regular induced subgraphs
• Induced 2-Regular Subgraphs in k-Chordal Cubic Graphs
• Induced subgraphs with many repeated degrees
• Bounds for regular induced subgraphs of strongly regular graphs
• Induced Subgraphs in Strongly Regular Graphs