A graph is γ_g-perfect exactly when it can be built from one vertex by adding complete graph components and by adding a vertex adjacent to everything except a perfect set of cliques; such graphs are recognizable in polynomial time.
On the equality of domination number and $ 2 $-domination number
1 Pith paper cite this work. Polarity classification is still indexing.
abstract
The 2-domination number $\gamma_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, $ \gamma_2(G) $ cannot be smaller than the domination number $ \gamma(G) $. We consider a large class of graphs and characterize those members which satisfy $\gamma_2=\gamma$. For the general case, we prove that it is NP-hard to decide whether $\gamma_2=\gamma$ holds. We also give a necessary and sufficient condition for a graph to satisfy the equality hereditarily.
fields
math.CO 1years
2019 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
Perfect graphs for domination games
A graph is γ_g-perfect exactly when it can be built from one vertex by adding complete graph components and by adding a vertex adjacent to everything except a perfect set of cliques; such graphs are recognizable in polynomial time.