Maximum independent sets in 3- and 4-regular Hamiltonian graphs
From MaRDI portal
Publication:709325
DOI10.1016/j.disc.2010.05.028zbMath1257.05116OpenAlexW2020320404MaRDI QIDQ709325
Vladimir I. Sarvanov, Gert Sabidussi, Herbert Fleischner
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
Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Eulerian and Hamiltonian graphs (05C45)
Related Items (13)
Multistage vertex cover ⋮ On bipartization of cubic graphs by removal of an independent set ⋮ Complexity and Polynomially Solvable Special Cases of QUBO ⋮ Feedback vertex set on Hamiltonian graphs ⋮ Temporal interval cliques and independent sets ⋮ Establishing herd immunity is hard even in simple geometric networks ⋮ Computational complexity of the vertex cover problem in the class of planar triangulations ⋮ Algorithm to find a maximum 2-packing set in a cactus ⋮ On the intersection graph of the disks with diameters the sides of a convex \(n\)-gon ⋮ On the maximum edge-pair embedding bipartite matching ⋮ On the maximum independent set problem in subclasses of subcubic graphs ⋮ A note on the fine-grained complexity of MIS on regular graphs ⋮ Large Independent Sets in Subquartic Planar Graphs
Cites Work
This page was built for publication: Maximum independent sets in 3- and 4-regular Hamiltonian graphs