The k-regular induced subgraph problem

DOI10.1016/J.DAM.2017.01.029MaRDI QIDQ1786867zbMATH OpenOpenAlexWikidataFDO

Authors Agostinho Agra, Geir Dahl, T. A. Haufmann, Sofia J. Pinheiro

Publication date 25 September 2018

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

Full work available at URL https://doi.org/10.1016/j.dam.2017.01.029

zbMATH Keywords

combinatorial optimizationinteger programmingregular induced graphsstrong-matchings

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Extremal problems in graph theory (05C35) Integer programming (90C10)

Recommendations

• Maximum \(k\)-regular induced subgraphs
• Maximum \(r\)-regular induced subgraph problem: fast exponential algorithms and combinatorial bounds
• Spectral Bounds for the k-Regular Induced Subgraph Problem
• Maximum regular induced subgraphs in 2P₃-free graphs
• Publication:4944970

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3668627 (Why is no real title available?)
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 3446921 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• scientific article; zbMATH DE number 3377258 (Why is no real title available?)
• A generalization of antiwebs to independence systems and their canonical facets
• A lower bound on the independence number of a graph
• An upper bound on the independence number of a graph computable in polynomial-time
• Eigenvalue bounds for independent sets
• Improving an upper bound on the size of \(k\)-regular induced subgraphs
• Induced matchings in intersection graphs.
• Laplacian spectral bounds for clique and independence numbers of graphs
• Lower bounds on the independence number in terms of the degrees
• Maximum \(k\)-regular induced subgraphs
• New insights on integer-programming models for the kidney exchange problem
• On the Shannon capacity of a graph
• On total unimodularity of edge-edge adjacency matrices
• Parameterized complexity of finding regular induced subgraphs
• Sharp bounds on the order, size, and stability number of graphs
• Spectral upper bounds for the order of a \(k\)-regular induced subgraph
• Spectral upper bounds on the size of \(k\)-regular induced subgraphs
• The Eigenvalues of a Graph and Its Chromatic Number

Cited in

(11)

• Induced 2-regular subgraphs in k-chordal cubic graphs
• Maximum regular induced subgraphs in 2P₃-free graphs
• \(k\)-edge subgraph problems
• MIP formulations for induced graph optimization problems: a tutorial
• Maximum weighted induced forests and trees: new formulations and a computational comparative review
• Maximum \(k\)-regular induced subgraphs
• scientific article; zbMATH DE number 4187869 (Why is no real title available?)
• Spectral Bounds for the k-Regular Induced Subgraph Problem
• New formulations and branch-and-cut procedures for the longest induced path problem
• Maximum \(r\)-regular induced subgraph problem: fast exponential algorithms and combinatorial bounds
• Maximum locally irregular induced subgraphs via minimum irregulators

This page was built for publication: The \(k\)-regular induced subgraph problem

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