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.

Answer 1

Theorem. A $k$-dense graph has at least $2^{k+1}-1$ vertices.

Proof. Let $L$ be a copy of the vertex set $V,$ with elements $l_v$ for $v\in V.$ Let $M$ be the bipartite graph on vertex set $V\cup L,$ with edges $wl_v$ whenever $w=v$ or $w$ is a child of $v.$ The $k$-dense condition implies that for any $L'\subseteq L$ with $|L'|\leq k,$ the set of neighbors $\Gamma(L')=\{v\in V\mid (\exists l_w\in L').vl_w\in E(M)\}$ has order at least $2|L'|+1.$ This implies that $M$ has no cycle $C$ of length $2k$ or less: taking $L'=C\cap L$ would give $|L'|\leq k$ and $|\Gamma(L')|\leq 2|L'|.$ So $M$ has girth at least $2(k+1),$ and both parts of $M$ have average degree $3.$ Hoory's bound [1] (alternate proof in [2]) gives $|V|\geq 1+2+4+\dots+2^k=2^{k+1}-1.$ $\Box$

Remark. I suspect, but haven't checked, that Hoory's bound is only sharp for regular graphs. The Feit-Higman theorem says that the only regular graphs attaining the bound above have girth $5,6,8,$ or $12,$ which means there could only be $k$-dense graphs of order $2^{k+1}-1$ for $k=2,3,5$ (and $k=1$). I believe you can construct a $k$-dense graph from a $(3,2k+2)$-cage (e.g. the Tutte 12-cage) quite easily by taking it as "$M$" and using a perfect matching to choose which vertices in $L$ should be labelled $l_v.$

[1] The Size of Bipartite Graphs with a Given Girth, Shlomo Hoory, https://www.sciencedirect.com/science/article/pii/S0095895602921234

[2] An entropy based proof of the Moore bound for irregular graphs, S. Ajesh Babu, Jaikumar Radhakrishnan, https://arxiv.org/abs/1011.1058