Search
Close this search box.

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

  • Research article

On Efficient Dominating Sets in Simplicial Graphs

Rommel Barbosa1, Peter Slater2
1 Instituto de Informatica – UFG Goiania – GO, Brazil
2Department of Mathematics and Department of Computer Science University of Alabama, Huntsville, 35899, USA
  • Published: 31/05/2012

Abstract

Determining whether or not a graph has an efficient dominating set (equivalently, a perfect code) is an NP-complete problem. Here we present a polynomial time algorithm to decide if a given simplicial graph has an efficient dominating set. However, the efficient domination number decision problem is NP-complete for simplicial graphs.

Keywords: Dominating sets; Efficient domination number; Simplicial graphs; Computational complexity.
Information
Guidelines
CP Initiatives
Follow CP
Facebook Twitter Linkedin
1970-2024 CP (Manitoba, Canada) unless otherwise stated.
Citation
Rommel Barbosa, Peter Slater. On Efficient Dominating Sets in Simplicial Graphs[J], Journal of Combinatorial Mathematics and Combinatorial Computing, Volume 081. 129-134. DOI: .