1
$\begingroup$

A $t$-fold dominating set in a simple undirected graph $G$ with vertex set $V$ is a subset $D\subseteq V$ such that each vertex of $V\setminus D$ has at least $t$ neighbours in $D$.

I am interested in the counterpart: a (proper) subset $M\subset V$ such that each vertex not in $M$ has at most $t$ neighbours in $M$. Is there a name for such subsets? If there is, could you please give me some references to papers dealing with this type of questions?

I am studying such sets in order to produce subgraphs of a graph with high minimal degree.

I only know that if $D\subset V$ has the property that each vertex not in $D$ has exactly $t$ neighbours in $D$ are called $t$-fold perfect dominating sets. (Leastwise for $t=1$, it is quite common to call them perfect dominating sets.)

New contributor
Tamás Héger is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$

Your Answer

Tamás Héger is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.