The \(k\)-regular induced subgraph problem

DOI10.1016/j.dam.2017.01.029zbMath1396.05053WikidataQ57736457 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 programming; combinatorial optimization; regular induced graphs; strong-matchings

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

90C10: Integer programming

90C27: Combinatorial optimization

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Related Items

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

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