Back to Search
Start Over
Partial Domination in Graphs
- Publication Year :
- 2017
-
Abstract
- A set $S\subseteq 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 $\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<br />Comment: First presented at the 48th Southeastern International Conference on Combinatorics, Graph Theory & Computing March 6-10, 2017
- Subjects :
- FOS: Mathematics
Mathematics - Combinatorics
Combinatorics (math.CO)
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....5a162c6dd067a22800a46269503219a0