The \(k\)-regular induced subgraph problem

DOI10.1016/j.dam.2017.01.029zbMath1396.05053OpenAlexW2590296153WikidataQ57736457 ScholiaQ57736457MaRDI QIDQ1786867

Geir Dahl, Sofia J. Pinheiro, Agostinho Agra, Torkel A. Haufmann

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

integer programmingcombinatorial optimizationregular induced graphsstrong-matchings

Mathematics Subject Classification ID

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

Related Items (3)

New formulations and branch-and-cut procedures for the longest induced path problem ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ Maximum weighted induced forests and trees: new formulations and a computational comparative review

Cites Work

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

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