Approximating the maximum size of a \(k\)-regular induced subgraph by an upper bound on the co-\(k\)-plex number

DOI10.1007/s10958-012-0742-2zbMath1254.05117OpenAlexW2085270790MaRDI QIDQ690542

Carlos J. Luz

Publication date: 28 November 2012

Published in: Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10958-012-0742-2

zbMATH Keywords

independent setsinduced matchings

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Uses Software

• SDPT3

Cites Work

• Unnamed Item
• Spectral upper bounds for the order of a \(k\)-regular induced subgraph
• A generalization of the Hoffman-Lovász upper bound on the independence number of a regular graph
• Maximum \(k\)-regular induced subgraphs
• Spectral upper bounds on the size of k-regular induced subgraphs
• Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
• A graph‐theoretic generalization of the clique concept
• A Convex Quadratic Characterization of the Lovász Theta Number

This page was built for publication: Approximating the maximum size of a \(k\)-regular induced subgraph by an upper bound on the co-\(k\)-plex number