Induced cycles in graphs

DOI10.1007/S00373-016-1713-ZMaRDI QIDQ503635zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 125455 (Why is no real title available?)
• scientific article; zbMATH DE number 863471 (Why is no real title available?)
• A Short Proof of the Factor Theorem for Finite Graphs
• Claw-free graphs---a survey
• Locating-total domination in claw-free cubic graphs
• Matching theory
• Maximum \(k\)-regular induced subgraphs
• Parameterized complexity of finding regular induced subgraphs
• Sparse regular induced subgraphs in \(2P_3\)-free graphs
• The Rectilinear Steiner Tree Problem is $NP$-Complete

Cited in

(13)

• Induced 2-regular subgraphs in k-chordal cubic graphs
• Large regular graphs with no induced \(2K_ 2\)
• Largest 2-regular subgraphs in 3-regular graphs
• Exact Solution Algorithms for the Chordless Cycle Problem
• Cover a 3-regular claw-free graph by induced matchings
• Induced path factors of regular graphs
• scientific article; zbMATH DE number 5139473 (Why is no real title available?)
• 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)