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.
Confidentially connected graphs, unbreakable graphs, open irredundant set, optimally efficient set.
Mihai TALMACIU, "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
All articles published by Studies in Informatics and Control (SIC) are published in accordance with the terms and conditions of the Creative Commons Attribution License (CC BY-NC-SA 4.0).