Contents

Ars Combinatoria

  • Research article

Independence and Irredundance in \(k\)-Regular Graphs

G.H. Fricke1, S.T. Hedetniemi2, D.P. Jacobs3
1 Department of Mathematics Wright State University Dayton, Ohio 45435
2Department of Computer Science Clemson University Clemson, SC 29634-1806
3Department of Computer Science Clemson University Clemson, SC 29634-1906
  • Published: 31/08/1998

Abstract

We show that for each fixed \(k \geq 3\), the \({INDEPENDENT \; SET}\) problem is \(NP\)-complete for the class of \(k\)-regular graphs. Several other decision problems, including \({IRREDUNDANT \; SET}\), are also \(NP\)-complete for each class of \(k\)-regular graphs, for \(k \geq 6\).

Citation
G.H. Fricke, S.T. Hedetniemi, D.P. Jacobs. Independence and Irredundance in \(k\)-Regular Graphs[J], Ars Combinatoria, Volume 049. 271-279. .