Scure 2-domination in graphs

Résumé

Abstract Let G = (V, E) be a simple graph. A set D ⊆ V is a dominating set of G if every vertex in V \ D is adjacent to at least one vertex in D. D is 2-dominating if every vertex in V \D has at least two neighbors in D. A secure dominating set S of a graph G is a dominating set with the property that every vertex u in V \S is adjacent to a vertex v ∈ S such that (S\{v}) ∪ {u} is a dominating set. In this paper, we define and study a new invariant of domination in graphs which is the secure 2-dominating set. A 2-dominating set S is secure 2-dominating if for every vertex u in V \S, ∃v ∈ (S ∩ N(u)) such that (S\{v}) ∪ {u} is a 2-dominating set. The secure 2-domination number γs2 (G) is equal to the minimum cardinality of a secure 2-dominating set. First, we establish lower and upper bounds on γs2 (G) of a graph and a triangle-free graph. Then we determine the secure 2-domination number γs2 (G) of paths and cycles. After, we study the complexity of secure 2-domination problem by proving that the determining of the parameters value is NP-complete, also for split and bipartite graphs. Finally, we provide an upper bound of parameter in terms of clique number and independent number for perfect graphs.

Citer ce document

Accès au document

Ce document est hébergé sur son dépôt institutionnel d'origine.

Auteur(s)

Statistiques

Consultations : 1

Téléchargements : 0