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

Autor:	Gert Sabidussi, Vladimir I. Sarvanov, Herbert Fleischner
Rok vydání:	2010
Předmět:	Combinatorics Discrete mathematics Indifference graph Chordal graph Independent set Odd graph Discrete Mathematics and Combinatorics Maximal independent set Longest path problem Theoretical Computer Science Mathematics Metric dimension Hamiltonian path problem
Zdroj:	Discrete Mathematics. 310:2742-2749
ISSN:	0012-365X
DOI:	10.1016/j.disc.2010.05.028
Popis:	Smooth 4-regular Hamiltonian graphs are generalizations of cycle-plus-triangles graphs. While the latter have been shown to be 3-choosable, 3-colorability of the former is NP-complete. In this paper we first show that the independent set problem for 3-regular Hamiltonian planar graphs is NP-complete, and using this result we show that this problem is also NP-complete for smooth 4-regular Hamiltonian graphs. We also show that this problem remains NP-complete if we restrict the problem to the existence of large independent sets (i.e., independent sets whose size is at least one third of the order of the graphs).
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::dc8b0f6025df909430045c1d0b365892 https://doi.org/10.1016/j.disc.2010.05.028 Zobrazit plný text záznamu Full Text from ScienceDirect