The k-regular induced subgraph problem

DOI10.1016/J.DAM.2017.01.029zbMATH Open1396.05053OpenAlexW2590296153WikidataQ57736457 ScholiaQ57736457MaRDI QIDQ1786867FDOQ1786867

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

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_3\)-free graphs
• Publication:4944970

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Shannon capacity of a graph
• Eigenvalue bounds for independent sets
• Parameterized complexity of finding regular induced subgraphs
• A generalization of antiwebs to independence systems and their canonical facets
• A lower bound on the independence number of a graph
• Lower bounds on the independence number in terms of the degrees
• Maximum \(k\)-regular induced subgraphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• New insights on integer-programming models for the kidney exchange problem
• Laplacian spectral bounds for clique and independence numbers of graphs
• Induced matchings in intersection graphs.
• On total unimodularity of edge-edge adjacency matrices
• The Eigenvalues of a Graph and Its Chromatic Number
• Title not available (Why is that?)
• Title not available (Why is that?)
• Improving an upper bound on the size of \(k\)-regular induced subgraphs
• An upper bound on the independence number of a graph computable in polynomial-time
• 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

Cited In (11)

• Induced 2-regular subgraphs in \(k\)-chordal cubic graphs
• Maximum regular induced subgraphs in \(2P_3\)-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
• Title not available (Why is that?)
• 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)