Pith. sign in

On the equality of domination number and $ 2 $-domination number

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
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 1

years

2019 1

verdicts

ACCEPT 1

representative citing papers

Perfect graphs for domination games

math.CO · 2019-08-26 · accept · novelty 6.0

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.

citing papers explorer

Showing 1 of 1 citing paper.

  • Perfect graphs for domination games math.CO · 2019-08-26 · accept · none · ref 3 · internal anchor

    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.