Title of article :
Maximum independent sets in 3- and 4-regular Hamiltonian graphs
Author/Authors :
Fleischner، نويسنده , , Herbert and Sabidussi، نويسنده , , Gert and Sarvanov، نويسنده , , Vladimir I.، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2010
Pages :
8
From page :
2742
To page :
2749
Abstract :
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).
Keywords :
NP-Completeness , Maximum independent set , Planar graphs , 3- or 4-regular graph
Journal title :
Discrete Mathematics
Serial Year :
2010
Journal title :
Discrete Mathematics
Record number :
1599428
Link To Document :
بازگشت