How many nodes in the smallest $k$-dense graph?

Question

Let's call a directed graph $k$-dense if:

• Each node has exactly two children (outgoing neighbors);
• Each two nodes have at least three different children (besides themselves);
• Each three nodes have at least four different children (besides themselves);
• ...
• Each $k$ nodes have at least $k+1$ different children (besides themselves);

What is the smallest number of nodes required for a $k$-dense graph?

Here are some special cases.

For $k=1$, the smallest number of nodes is $3$:

1->[2,3],   2->[3,1],   3->[1,2]

For $k=2$, the smallest number of nodes is $7$. To see this we can build the graph greedily based on the following constraint: a node's child must be different than its parent(s) and is sibling(s). Why? Because a node and its parent together must have three children besides themselves.

• $1$ has two children: call them $2$ and $3$.
• $2$ must have two children different than its parent ($1$) and sibling ($3$): call them $4$ and $5$.
• $3$ must have two children different than its parent ($1$) and sibling ($2$). The first can be $4$. Now, $3$ and $2$ together have only two children besides themselves ($4$ and $5$), so $3$ must have another different child - call it $6$.
• $4$ must have two children different than its parents ($2$ and $3$) and siblings ($5$ and $6$). The first can be $1$ and the second must be new - call it $7$.
• $5$ must have two children different than its parent ($2$) and siblings ($4$). The first can be $1$. The second cannot be one of $1$'s children ($2$ and $3$) or siblings ($7$) so it must be $6$.
• $6$ must have two children different than its parents ($3$ and $5$) and siblings ($4$ and $1$). These must be $2$ and $7$.
• $7$ must have two children different than its parents ($4$ and $6$) and siblings ($2$ and $1$). These must be $3$ and $5$.

All in all, we have the following $2$-dense graph with $n=7$ nodes:

1->[2,3]  2->[4,5]  3->[4,6]  4->[1,7]  5->[1,6]  6->[2,7]  7->[3,5]

For $k=3$, I used a similar greedy algorithm (with more constraints) to construct the following graph:

 1->[2,3]    2->[4,5]    3->[6,7]    4->[6,8]     5->[7,9]
 6->[10,11]  7->[12,13]  8->[1,9]    9->[10,14]  10->[2,12]  
11->[1,13]  12->[8,15]  13->[4,14]  14->[3,15]   15->[5,11]

I used a computer program to check all possibilities with at most $14$ nodes, and found none, so (assuming my program is correct) $n=15$ is the minimum number required for $k=3$.

This hints that the minimum number of nodes in a $k$-dense graph should be: $2^{k+1}-1$. Is this true?

What is the smallest number of nodes required for general $k$?

UPDATE 1: I have just learned about vertex expansion. It seems closely related but I am still not sure how exactly.