Induced cycles in graphs

DOI10.1007/S00373-016-1713-ZzbMATH Open1353.05071arXiv1406.0606OpenAlexW1808305725MaRDI QIDQ503635FDOQ503635

Authors: Michael A. Henning, Felix Joos, Christian Löwenstein, Thomas Sasse 

Publication date: 13 January 2017

Published in: Graphs and Combinatorics (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/1406.0606

Recommendations

• Induced 2-regular subgraphs in \(k\)-chordal cubic graphs
• Induced path factors of regular graphs
• Large Nearly Regular Induced Subgraphs
• Large regular graphs with no induced \(2K_ 2\)
• Longest cycles in regular 2-connected claw-free graphs

zbMATH Keywords

matchinginduced cycleclaw-free1-extendabilityinduced regular subgraphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Paths and cycles (05C38)

Cites Work

• Matching theory
• Parameterized complexity of finding regular induced subgraphs
• Claw-free graphs---a survey
• Sparse regular induced subgraphs in \(2P_3\)-free graphs
• Maximum \(k\)-regular induced subgraphs
• Title not available (Why is that?)
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• A Short Proof of the Factor Theorem for Finite Graphs
• Locating-total domination in claw-free cubic graphs
• Title not available (Why is that?)

Cited In (13)

• Induced 2-regular subgraphs in \(k\)-chordal cubic graphs
• Large regular graphs with no induced \(2K_ 2\)
• Exact Solution Algorithms for the Chordless Cycle Problem
• Largest 2-regular subgraphs in 3-regular graphs
• Induced path factors of regular graphs
• Cover a 3-regular claw-free graph by induced matchings
• Title not available (Why is that?)
• Independent point-set domination in line graphs
• Inducing Measures by Cyclic Networks
• Induced subgraphs of a tree with constraint degree
• On the inducibility of cycles
• On the inducibility of cycles
• Induced Cycle Path Number of Graphs

This page was built for publication: Induced cycles in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q503635)