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$.
10
questions
5
votes
1
answer
239
views
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
4
votes
2
answers
216
views
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$, ...
- 6,832
3
votes
0
answers
191
views
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 ...
- 270
3
votes
0
answers
304
views
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 ...
- 31
2
votes
1
answer
181
views
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?
- 6,832
1
vote
0
answers
90
views
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-...
- 11
1
vote
0
answers
64
views
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!
0
votes
1
answer
48
views
Minimal dominating sets in flat graphs
Suppose that $G=(V,E)$ is a simple, undirected graph. We say that $D\subseteq V$ is dominating if for all $v\in V\setminus D$ there is $d\in D$ such that $\{v,d\}\in E$. We say $D$ is minimal ...
- 44.5k
0
votes
1
answer
57
views
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$.
...
- 44.5k
0
votes
0
answers
20
views
Domination number and induced chromatic number
Graph theory is not really my field and hopefully I am not asking something silly.
Let $G=(V,E)$ be a graph (say connected and regular because it is the case I am interested in, but I am curious also ...
- 886