Determination of the Optimally Efficient Sets in Special Classes of Graphs

Mihai Tălmaciu
“Vasile Alecsandri” University
Bacău

Abstract:

A dominating set is said to be an efficient dominating set if, for every vertex v ∈ V, |N[v] ∩ S| = 1 [1]. A set S is called open irredundant if, for every vertex u ∈ S, there exists a vertex v ∈ V ? S for which N(v) ∩ S = {u}, in which case we say that u efficiently dominates v. There exists a polynomial time algorithm for finding an optimally efficient set in an arbitrary graph. We determine directly the optimally efficient sets in confidentially connected graphs and unbreakable graphs. Also, we determine directly the open irredundant set, closed neighborhood packing set, the influence of a set in confidentially connected graphs and unbreakable graphs.

Keywords:

Confidentially connected graphs, unbreakable graphs, open irredundant set, optimally efficient set.

>>Full text
CITE THIS PAPER AS:
Mihai TĂLMACIU, Determination of the Optimally Efficient Sets in Special Classes of Graphs, Studies in Informatics and Control, ISSN 1220-1766, vol. 21 (4), pp. 447-452, 2012. https://doi.org/10.24846/v21i4y201211