Spectral Bounds for the k-Regular Induced Subgraph Problem

DOI10.1007/978-3-319-49984-0_7MaRDI QIDQ4554522zbMATH OpenOpenAlexFDO

Authors Sofia J. Pinheiro, D. M. Cardoso

Publication date 14 November 2018

Published in Springer Proceedings in Mathematics & Statistics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-49984-0_7

zbMATH Keywords

spectral graph theorycombinatorial optimizationmaximum \(k\)-regular induced subgraphs

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Combinatorial optimization (90C27) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Extremal problems in graph theory (05C35)

Recommendations

• Spectral upper bounds on the size of \(k\)-regular induced subgraphs
• Spectral upper bounds for the order of a \(k\)-regular induced subgraph
• The k-regular induced subgraph problem
• Improving an upper bound on the size of \(k\)-regular induced subgraphs
• Bounds for regular induced subgraphs of strongly regular graphs
• Approximating the maximum size of a \(k\)-regular induced subgraph by an upper bound on the co-\(k\)-plex number
• Maximum \(r\)-regular induced subgraph problem: fast exponential algorithms and combinatorial bounds
• Maximum \(k\)-regular induced subgraphs
• Spectral bounds for the \(k\)-independence number of a graph
• Parameterized complexity of finding regular induced subgraphs

Cites work

• scientific article; zbMATH DE number 3668627 (Why is no real title available?)
• scientific article; zbMATH DE number 3528270 (Why is no real title available?)
• scientific article; zbMATH DE number 740754 (Why is no real title available?)
• scientific article; zbMATH DE number 1054729 (Why is no real title available?)
• scientific article; zbMATH DE number 956839 (Why is no real title available?)
• An introduction to the theory of graph spectra
• Eigenvalue bounds for independent sets
• Graphs with least eigenvalue \(-2\) attaining a convex quadratic upper bound for the stability number
• Interlacing eigenvalues and graphs
• Laplacian spectral bounds for clique and independence numbers of graphs
• Maximum \(k\)-regular induced subgraphs
• On conjectures involving second largest signless Laplacian eigenvalue of graphs
• On the Shannon capacity of a graph
• Signless Laplacians of finite 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

(6)

• Improving an upper bound on the size of \(k\)-regular induced subgraphs
• Approximating the maximum size of a \(k\)-regular induced subgraph by an upper bound on the co-\(k\)-plex number
• The k-regular induced subgraph problem
• Spectral upper bounds on the size of \(k\)-regular induced subgraphs
• Maximum \(k\)-regular induced subgraphs
• Spectral upper bounds for the order of a \(k\)-regular induced subgraph

This page was built for publication: Spectral Bounds for 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 Q4554522)