2016/12/25 by Csilla Bujtás, Bujtás, Csilla, Szilárd Jaskó +1 · 1 citation
Computer Science · #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · doi:10.48550/arxiv.1612.08301
openalex publication_date 2016/12/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In a graph G, a set D⊆ V(G) is called 2-dominating set if each vertex not in D has at least two neighbors in D. The 2-domination number γ2(G) is the minimum cardinality of such a set D. We give a method for the construction of 2-dominating sets, which also yields upper bounds on the 2-domination number in terms of the number of vertices, if the minimum degree δ(G) is fixed. These improve the best earlier bounds for any 6 ≤ δ(G) ≤ 21. In particular, we prove that γ2(G) is strictly smaller than n/2, if δ(G) ≥ 6. Our proof technique uses a weight-assignment to the vertices where the weights are changed during the procedure.