Partial domination in graphs

MaRDI QIDQ4636252zbMATH OpenFDO

Authors Benjamin M. Case, Stephen T. Hedetniemi, Drew J. Lipman, Renu C. Laskar

Publication date 23 April 2018

Full work available at URL https://arxiv.org/abs/1705.03096

zbMATH Keywords

dominating setdomination numberpartial dominationpartial domination number

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: A set $SsubseteqV$ is a dominating set of $G$ if every vertex in $V-S$ is adjacent to at least one vertex in $S$. The domination number $gamma(G)$ of $G$ equals the minimum cardinality of a dominating set $S$ in $G$; we say that such a set $S$ is a $gamma$-set. The single greatest focus of research in domination theory is the determination of the value of $gamma(G)$. By definition, all vertices must be dominated by a $gamma$-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

Recommendations

• 1/2-domination in graphs
• Independent partial domination
• -graphs of graphs
• Domination value in graphs
• scientific article; zbMATH DE number 1161247

Cited in

(6)

• 1/2-domination in graphs
• Partial domination in the join, corona, lexicographic and Cartesian products of graphs
• Independent partial domination
• Partial domination -- the isolation number of a graph
• Approximating partially bounded degree deletion on directed graphs
• Partial domination in supercubic graphs

This page was built for publication: Partial domination in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4636252)