Graphs with disjoint 2-dominating sets

2021/03/04 by Michael A. Henning, Henning, Michael A., Jerzy Topp +1
Computer Science · #05C69 #05C85 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.2103.03053

openalex publication_date 2021/03/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A subset D⊆ V_G is a dominating set of G if every vertex in V_G∖ D has a neighbor in D, while D is a 2-dominating set of G if every vertex belonging to V_G∖ D is joined by at least two edges with a vertex or vertices in D. A graph G is a (2,2)-dominated graph if it has a pair (D,D') of disjoint 2-dominating sets of vertices of G. In this paper we present two characterizations of minimal (2,2)-dominated graphs.

Related

• Disjoint dominating and 2-dominating sets in graphs
• Disjoint Dominating and 2-Dominating Sets in Graphs: Hardness and Approximation results
• Bounds on the 2-domination number
• On the equality of domination number and 2 -domination number
• On 2-Movable Domination in the Join and Corona of Graphs