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.