2017/05/08 by Benjamin M. Case, Case, Benjamin M., Stephen T. Hedetniemi +5
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.1705.03096
openalex publication_date 2017/05/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A set S⊆ V is a dominating set of G if every vertex in V - S is adjacent to at least one vertex in S. The domination number γ(G) of G equals the minimum cardinality of a dominating set S in G; we say that such a set S is a γ-set. The single greatest focus of research in domination theory is the determination of the value of γ(G). By definition, all vertices must be dominated by a γ-set. In this paper we propose relaxing this requirement, by seeking sets of vertices that dominate a prescribed fraction of the vertices of a graph. We focus particular attention on 1/2 domination, that is, sets of vertices that dominate at least half of the vertices of a graph G. Keywords: partial domination, dominating set, partial domination number, domination number