Induced 2-regular subgraphs in k-chordal cubic graphs

DOI10.1016/J.DAM.2016.01.009zbMATH Open1333.05203arXiv1406.2438OpenAlexW1542253437MaRDI QIDQ266935FDOQ266935

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)

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.

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

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_3\)-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

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)

Cites Work

• Parameterized complexity of finding regular induced subgraphs
• Treewidth for graphs with small chordality
• Sparse regular induced subgraphs in \(2P_3\)-free graphs
• Dirac-type characterizations of graphs without long chordless cycles
• Maximum \(k\)-regular induced subgraphs
• A Dirac-type characterization of \(k\)-chordal graphs
• Title not available (Why is that?)
• Fair domination in graphs
• Title not available (Why is that?)
• Induced cycles in graphs
• Fast Exponential Algorithms for Maximum r-Regular Induced Subgraph Problems

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)