Maximum independent sets in 3- and 4-regular Hamiltonian graphs

DOI10.1016/j.disc.2010.05.028zbMath1257.05116MaRDI QIDQ709325

Herbert Fleischner, Gert Sabidussi, Vladimir I. Sarvanov

Publication date: 18 October 2010

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

Full work available at URL: https://doi.org/10.1016/j.disc.2010.05.028

zbMATH Keywords

planar graphs; NP-completeness; maximum independent set; 3- or 4-regular graph

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

05C10: Planar graphs; geometric and topological aspects of graph theory

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

05C45: Eulerian and Hamiltonian graphs