2019/07/18 by Gülnaz Boruzanlı Ek̇inċi, Ekinci, Gülnaz Boruzanlı, Csilla Bujtás +1
Computer Science · #05C69 #05C75 #68Q25 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.1907.07866
openalex publication_date 2019/07/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The 2-domination number γ2(G) of a graph G is the minimum cardinality of a set D ⊆ V(G) for which every vertex outside D is adjacent to at least two vertices in D . Clearly, γ2(G) cannot be smaller than the domination number γ(G) . We consider a large class of graphs and characterize those members which satisfy γ2=γ. For the general case, we prove that it is NP-hard to decide whether γ2=γ holds. We also give a necessary and sufficient condition for a graph to satisfy the equality hereditarily.