Spectral Bounds for the k-Regular Induced Subgraph Problem

DOI10.1007/978-3-319-49984-0_7zbMATH Open1400.05144OpenAlexW2593452134MaRDI QIDQ4554522FDOQ4554522

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

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

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)

Cites Work

• Signless Laplacians of finite graphs
• Interlacing eigenvalues and graphs
• An introduction to the theory of graph spectra
• On the Shannon capacity of a graph
• Eigenvalue bounds for independent sets
• Maximum \(k\)-regular induced subgraphs
• Title not available (Why is that?)
• On conjectures involving second largest signless Laplacian eigenvalue of graphs
• Title not available (Why is that?)
• Laplacian spectral bounds for clique and independence numbers of graphs
• Title not available (Why is that?)
• Graphs with least eigenvalue \(-2\) attaining a convex quadratic upper bound for the stability number
• Title not available (Why is that?)
• Spectral upper bounds for the order of a \(k\)-regular induced subgraph
• Title not available (Why is that?)
• 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)