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

DOI10.1016/j.endm.2009.02.002zbMath1267.05162MaRDI 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 sets; graph spectra; induced matchings; 2-factors; programming involving graphs

Mathematics Subject Classification ID

90C20: Quadratic programming

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Spectral Bounds for the k-Regular Induced Subgraph Problem, 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 cost of segregation in (social) networks, 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