Skip to main content
Source Link
Xorwell
  • 424
  • 2
  • 9

Directed Hypercube Minimal Cuts

If $[n]:=\{1,2,\ldots, n\}$ for some $n\in\mathbb{N}$, then the hypercube digraph of dimension $n$, denoted $H_n$, is the graph whose set of vertices is the power-set $\wp([n])$ where two vertices $U,V\subseteq [n]$ are adjacent and oriented as $\langle U, V\rangle$ if and only if there exists some $q\in [n]$ such that $U=V\setminus \{q\}$.

A cut $C$ of $H_n$ is a subset of the vertex set $C\subseteq \wp([n])\setminus \{\emptyset, [n]\}$ such that that (1) it does not contains neither the bottom vertex $\emptyset$ nor the top vertex $[n]$ (2) there exists no directed path from $\emptyset$ to $[n]$ in the subgraph of $H_n$ induced by $\wp([n])\setminus C$, i.e. there is no directed path in $H_n$ that goes from the bottom vertex $\emptyset$ to the top vertex $[n]$ simultaneously avoiding all vertices of $C$.

A cut $C$ is minimal when for every $S\subsetneq C$ we have that $S$ is not a cut.

Q. Is it known how to count and/or generate the family of minimal cuts on the directed hypercube graphs ?

Q. Let $\gamma(n)$ be the number of minimal cuts of $H_n$, is this integer sequence already known in the literature ?

Q. Is it anything known on minimal cuts ?