Induced 2-regular subgraphs in k-chordal cubic graphs

DOI10.1016/J.DAM.2016.01.009MaRDI QIDQ266935zbMATH OpenOpenAlexFDO

Authors Michael A. Henning, Felix Joos, Dieter Rautenbach, Christian Löwenstein

Publication date 7 April 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

independent setinduced cycleinduced matchinginduced regular subgraph

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We show that a cubic graph $G$ of order $n$ has an induced $2$-regular subgraph of order at least a) $fracn-24-frac4k$, if $G$ has no induced cycle of length more than $k$, b) $frac5n+68$, if $G$ has no induced cycle of length more than $4$, and $n>6$, and c) $left(frac14+epsilonight)n$, if the independence number of $G$ is at most $left(frac38-epsilonight)n$. To show the second result we give a precise structural description of cubic $4$-chordal graphs.

Recommendations

• scientific article; zbMATH DE number 867630
• The k-regular induced subgraph problem
• On induced subgraphs of the cube
• On 2-regular subgraphs in polyhedral graphs
• Maximum regular induced subgraphs in 2P₃-free graphs
• Sparse regular induced subgraphs in \(2P_3\)-free graphs
• On regular induced subgraphs of generalized polygons
• Induced subgraphs of hypercubes
• Induced matchings in subcubic graphs
• Bounds for regular induced subgraphs of strongly regular graphs

Cites work

• scientific article; zbMATH DE number 125455 (Why is no real title available?)
• scientific article; zbMATH DE number 2159659 (Why is no real title available?)
• A Dirac-type characterization of \(k\)-chordal graphs
• Dirac-type characterizations of graphs without long chordless cycles
• Fair domination in graphs
• Fast Exponential Algorithms for Maximum r-Regular Induced Subgraph Problems
• Induced cycles in graphs
• Maximum \(k\)-regular induced subgraphs
• Parameterized complexity of finding regular induced subgraphs
• Sparse regular induced subgraphs in \(2P_3\)-free graphs
• Treewidth for graphs with small chordality

Cited in

(3)

• Induced cycles in graphs
• Induced path factors of regular graphs
• Partitioning the vertices of a cubic graph into two total dominating sets

This page was built for publication: Induced 2-regular subgraphs in \(k\)-chordal cubic graphs

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