Spectral upper bounds on the size of k-regular induced subgraphs

DOI10.1016/j.endm.2009.02.002zbMath1267.05162OpenAlexW2059018804MaRDI QIDQ2839204

Sofia J. Pinheiro, Domingos Moreira Cardoso

Publication date: 4 July 2013

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2009.02.002

zbMATH Keywords

independent setsgraph spectrainduced matchings2-factorsprogramming involving graphs

Mathematics Subject Classification ID

Quadratic programming (90C20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

Spectral Bounds for the k-Regular Induced Subgraph Problem ⋮ The cost of segregation in (social) networks ⋮ On irregularity indices and main eigenvalues of graphs and their applicability ⋮ Approximating the maximum size of a \(k\)-regular induced subgraph by an upper bound on the co-\(k\)-plex number ⋮ Integral graphs and \((k,\tau )\)-regular sets ⋮ Spectral upper bounds for the order of a \(k\)-regular induced subgraph ⋮ The \(k\)-regular induced subgraph problem ⋮ Some new aspects of main eigenvalues of graphs

Cites Work

• Unnamed Item
• Equitable bipartitions of graphs and related results
• Maximum \(k\)-regular induced subgraphs
• On the Shannon capacity of a graph
• The Eigenvalues of a Graph and Its Chromatic Number

This page was built for publication: Spectral upper bounds on the size of k-regular induced subgraphs