Spectral Bounds for the k-Regular Induced Subgraph Problem

DOI10.1007/978-3-319-49984-0_7zbMath1400.05144OpenAlexW2593452134MaRDI QIDQ4554522

Sofia J. Pinheiro, Domingos Moreira 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

combinatorial optimizationspectral graph theorymaximum \(k\)-regular induced subgraphs

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Signless Laplacians of finite graphs
• Eigenvalue bounds for independent sets
• On conjectures involving second largest signless Laplacian eigenvalue of graphs
• Spectral upper bounds for the order of a \(k\)-regular induced subgraph
• Interlacing eigenvalues and graphs
• 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
• Graphs with least eigenvalue -2 attaining a convex quadratic upper bound for the stability number
• On the Shannon capacity of a graph

This page was built for publication: Spectral Bounds for the k-Regular Induced Subgraph Problem