On the equality of domination number and 2-domination number
Copyright policy )On the equality of domination number and 2-domination number
The 2-domination number $��_2(G)$ of a graph $G$ is the minimum cardinality of a set $ D \subseteq 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.
Submitted to a journal in July 2018
- University of Pannonia Hungary
- University of Ljubljana Slovenia
- Ege University Turkey
- Faculty of Information Technology Australia
computational complexity, 2-domination number, 05C69, 05C75, 68Q25, Analysis of algorithms and problem complexity, domination number, K-Domination, Annihilation Number, info:eu-repo/classification/udc/519.17, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Bounds, Transversal Numbers, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, Structural characterization of families of graphs, Combinatorics (math.CO), Graphs, Mathematics, hereditary property
computational complexity, 2-domination number, 05C69, 05C75, 68Q25, Analysis of algorithms and problem complexity, domination number, K-Domination, Annihilation Number, info:eu-repo/classification/udc/519.17, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Bounds, Transversal Numbers, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, Structural characterization of families of graphs, Combinatorics (math.CO), Graphs, Mathematics, hereditary property
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).1 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!