Questions tagged [graph-domination]

Given a graph $G$, a dominating set is a set of vertices $D$ such that every vertex of $G$ is in $D$ or adjacent to a vertex in $D$.

Filter by
Sorted by
Tagged with
1 vote
0 answers

Meaning of L-reduction from Dominating set problem

We are working in a variation of Locating dominating sets. Recently, we realized that the reduction from dominating set to our problem in proving its NP-completeness turns out to be also an L-...
0 votes
1 answer

Dominating vertex sets in hypergraphs

Let $H=(V,E)$ be a hypergraph such that $\bigcup E = V$. For $D\subseteq V$ we set $N_D = \bigcup\{e\in E: D\cap e\neq \emptyset\}$. We say that $D\subseteq V$ is dominating if $N_D = V$. ...
5 votes
1 answer

Independent domination number for grid graphs

Let $G_{n,m}$ be the $n \times m$ grid graph, i.e. $G= P_n \Box P_m$, and $T_{n,m}$ the $n\times m$ torus grid graph, i.e. $G= C_n \Box C_m$, where $P_n$ and $C_n$ indicate the path graph of length $n$...
  • 418
3 votes
0 answers

Properties of a smallest tournament with domination number $k$

For some tournament $T$, let $\gamma(T)$ denote the cardinality of a smallest dominating set of $T$. Denote by $f(k)$ the minimum number of vertices of a tournament $T$ having $\gamma(T) = k$. From ...
4 votes
2 answers

Is the domination number of a combinatorial design determined by the design parameters?

Let $D$ be a $(v,k,\lambda)$-design. By the domination number of $D$ I mean the domination number $\gamma(L(D))$ of the bipartite incidence graph of $D$. Is $\gamma(L(D))$ determined only by $v,k$, ...
2 votes
1 answer

Is the domination number NP for non-bipartite graphs?

Calculating the domination number is an NP-Hard problem. Does it remain NP-Hard if we restrict it to non-bipartite graphs?
1 vote
0 answers

Complexity of in-dominating set

Is the decision problem In-Dominating Set NP-complete for digraphs of regular out-degree (greater than $\frac{n-2}{4}$, in particular)? -- I'm mainly looking for a reference. Thanks for any answer!
3 votes
0 answers

Domination number of hamming graphs

The problem of finding the domination number of Hamming graph $H(3, 2n)$ ($n$ is an integer) was given as a homework for my discrete math class. I didn't manage to solve the question. But later the ...