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

1. Introduction

This article is motivated because there is only a polynomial time algorithm for finding an optimally efficient set in an arbitrary graph, and we determine it directly for special classes of graphs. Also, in [13] domination and irredundance parameters for some graphs have been extensively studied. For a survey see [9].

The efficiency of a set S ⊆ V in a graph G=(V,E), is defined as ε(S) = |{v ∈ V −S: |N(v)∩ S| = 1}|. The efficiency of a graph, denoted ε(G), is defined to equal the maximum efficiency of a set S ⊆ V in G [3]. A dominating set for a graph G = (V, E) is a subset D of V such that every vertex not in D is joined to at least one member of D by some edge. That is, a set D is a dominating set if |N[v] ∩ D| ≥ 1 for all vertices v in V (G). The domination number γ(G) is the number of vertices in the smallest dominating set of G. A subset S V (G) is called a k -packing, if for any two distinct vertices u, v in S , we have d(u, v) > k. A set S is a closed neighborhood packing if for each u, v S, u v we have N[u] ∩ N[v] = . That is, a set S is a closed neighborhood packing if |N[v] ∩ S| ≤ 1 for all vertices v V (G). The packing number ρ(G) is the size of the largest closed neighborhood packing. For all graphs G, 1 ≤ ρ(G) ≤ n . The only graphs with ρ(G) = n are graphs with no edges.

A dominating set S is called a perfect dominating set if every vertex v ∈ V − S is adjacent to exactly one vertex in S [4]. A dominating set is said to be an efficient dominating set if for every vertex v ∈ V, |N[v] ∩ S| = 1 [1]. The efficient domination number of a graph, denoted F(G), is the maximum number of vertices that can be dominated by a set S that dominates each vertex at the most once. A graph G of order n = |V (G)| has an efficient dominating set if and only if F(G) = n.

A graph is efficient if and only if there exists an efficient dominating set. That is, a graph is efficient if and only if there exists a set S which is both dominating and a closed neighborhood packing.

If a graph G is efficient, then ρ(G) = γ(G) [12] .

The influence of S is defined in [8] to be
I(S) = ,

where deg(v) = |N(v)|, the cardinality of the open neighborhood of v.

Thus, the efficient domination number of a graph G is F(G)=max{I(S): S is a packing}=max{ and u, v S implies d(u, v) 3}. An F(G) -set S is a set that is both a packing and I(S) = F(G).

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 [7].

The upper open irredundance number, denoted OIR(G), equals the maximum number of vertices in an open irredundant set. Thus, OIR(G) equals the maximum number of vertices that can simultaneously and successfully broadcast a message in an Ethernet graph.

By contrast, the efficiency of a graph G equals the maximum number of vertices that can simultaneously receive a broadcast message in an Ethernet graph.

A set S is optimally efficient if two conditions are met: (i) for every vertex v ∈ V − S, ε(S ∪ {v}) ≤ ε(S), and (ii) for every vertex u ∈ S, ε(S − {u}) < ε(S).

In a network, the communication is said to be “confidential” if a message can be passed between any two vertices, without being intercepted by a third vertex. In the language of graph theory, this property stands for confidential connectivity.

There exists a polynomial time algorithm for finding an optimally efficient set in an arbitrary graph [10].

We determine directly the optimally efficient sets in confidentially connected graphs and unbreakable graphs.

Such communications are shown in [11].

REFERENCES

Bange, D. W., A. E. Barkauskas, P. J. Slater, Efficient Dominating Sets in Graphs, in: R. D. Ringeisen, F. S. Roberts (Eds.), Applications of Discrete Mathematics, SIAM, Philadelphia, PA, 1988, pp. 189-199.
Berge, C., Graphs, North-Holland, Amsterdam. 1985.
Bernhard, P. J., S. T. Hedetniemi, D. P. Jacobs, Efficient Sets in Graphs, Discrete Applied Mathematics, vol. 44, 1993, pp. 99-108.
Cockayne, E. J., B. L. Hartnell, S. T. Hedetniemi, R. Laskar, Perfect Domination in Graphs, Journal of Combinatorics, Information & System Sciences, vol. 18, 1993, pp. 136-148.
Croitoru, C., E. Olaru, M. Talmaciu, Confidentially Connected Graphs, The annals of the University “Dunarea de Jos” of Galati, Proceedings of the international conference “The risk in contemporany economy”, Supplement to Tome XVIII (XXII), 2000.
Croitoru, C., M. Talmaciu, On Confidentially Connected Graphs, Buletinul Ştiinţific al Universităţii din Baia Mare. Seria B, Matematică – Informatică, vol. XVI, Nr. 1, 2000, pp. 13-16.
Farley, A. M., N. Schacham, Senders in Broadcast Networks: Open Irredundancy in Graphs, Congressus Numerantium, vol. 38, 1983, pp. 47-57.
Grinstead, D. L., P. J. Slater, Fractional Domination and Fractional Packing in Graphs, Congressus Numerantium, vol. 71, 1990, pp. 153-172.
Hedetmiemi, S. M., S. T. Hedetmiemi, R. Reynolds, Combinatorial Problems on Chessboards: II, In T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, editors, Domination in Graphs: Advanced Topics, Marcel Kekker, Inc. 1997.
Hedetniemi, S. M., S. T. Hedetniemi, H. Jiang, K. E. Kennedy, A. A. McRae, A Self-stabilizing Algorithm for Optimally Efficient Sets in Graphs, Information Processing Letters, vol. 112, 2012, pp. 621-623.
Page, T., An Artificial Neural Network (ANN) in Electronic Product Design, Studies in Informatics and Control, vol. 21(3), 2012, pp. 259-266. ISSN 1220-1766
Rubalcaba, R. R., A. Schneider, P. J. Slater, A Survey on Graphs which Have Equal Domination and Closed Neighborhood Packing Numbers, AKCE International Journal of Graphs and Combinatorics., vol. 3, No. 2, 2006, pp. 93-114.
Sinko, A. P. J. Slater, An Introduction to Influence Parameters for Chessboard Graphs, Congressus Numerantium, vol. 172, 2005, pp. 15-27.
Talmaciu, M., Decomposition Problems in the Graph Theory with Applications in Combinatorial Optimization – Ph. D. Thesis, University “Al. I. Cuza” Iaşi, Romania, 2002.
Talmaciu, M., E. Nechita, Recognition Algorithm for Diamond-free Graphs, Informatica, vol. 18, 2007, pp. 457-462.
Talmaciu, M., E. Nechita, G. C. Crisan, A Recognition Algorithm for a Class of Partitionable Graphs that Satisfies the Normal Graph Conjecture, Studies in Informatics and Control, vol. 18, 2009, pp. 349-354.