When generating a random k-out k-regular directed graph, each node chooses randomly a distinct set of k nodes and creates k out-edges to them.
I've only found results to my first question where $P = 1$ when $n \to \infty$ whp, where we find an asymptotic threshold for $k$. But I'm interested in a fixed and small number $n$, and I'm interested in a 100% probability to generate a connected graph in the end.
If I know the number of total nodes (let's say $n=10$). What is the minimum $k$ so that the graph will have 100% of probability to stay weakly connected?
Do we have a simple formula if I add a constraint on the vertex-connectivity? If I want to add the constraint that the graph should have a 2-connectivity, i.e. I can lose at most one node without disconnecting the graph, what is the minimum $k$ (number of distinct neighbors chosen randomly) ensuring 100% probability to generate that?
If the graph were not weakly connected, there would have to be a connected component with at most $\lfloor \frac n2 \rfloor$ nodes. (If all components were larger than this, then since we have at least $2$ components, we'd end up with more than $n$ nodes total.)
In this component, each node can have edges to at most $\lfloor \frac n2 \rfloor - 1$ other nodes, so this can only happen (but can still happen!) when $k \le \lfloor \frac n2 \rfloor - 1$.
When $k \ge \lfloor \frac n2 \rfloor$, the graph is guaranteed to be weakly connected.
For the $2$-connected graph, I am assuming you still want weak connectivity. Here, suppose the graph is not $2$-connected: deleting some node $v$ disconnects the graph. Then $G-v$ has $n-1$ nodes, so there is a connected component with at most $\lfloor \frac {n-1}2 \rfloor$ nodes.
A node in that component of $G-v$ can have edges to at most $\lfloor \frac {n-1}2 \rfloor - 1$ other nodes in that component, but it can also have an edge to $v$. This can still happen when $k = \lfloor \frac {n-1}2 \rfloor$.
When $k \ge \lfloor \frac {n-1}2 \rfloor + 1$, the graph is guaranteed to be $2$-connected.
Similarly, when $k \ge \lfloor \frac {n-c+1}2 \rfloor + c -1$, the graph is guaranteed to be $c$-connected.