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

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.

• Am I missing something, or is the fact that your graphs are directed irrelevant? Aug 11, 2016 at 12:27
• My bad, I just understood your notation for your nodes and arrows. I thought $[i,j]$ meant that you put an arrow from $i$ to $j$... Aug 11, 2016 at 14:25
• I'm not sure about the least, but if I haven't any mistakes in my reasoning this is always doable for $n=2^{k+1}-1$, where $n$ is the number of nodes.
– Jal
Aug 13, 2016 at 18:10
• Is it even clear that your greedy algorithm produces the smallest number of nodes?
Aug 14, 2016 at 1:44
• @Tad I checked that 7 is the smallest for $k=2$. But I am not sure that a greedy algorithm is optimal for $k>2$. Aug 14, 2016 at 21:24

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  (alternate proof in ) 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.$$
• So the only thing left to confirm is that there exists some $k \in \mathbb{N}$ such that the smallest $k$-dense graph has strictly more than $2^{k+1} - 1$ nodes. Or perhaps even stronger, to confirm your remark @Dap that $\forall k \in \mathbb{N} \setminus \{ 1,2,3,5 \}$ the smallest $k$-dense graph has strictly more than $2^{k+1} - 1$ nodes. Feb 19, 2019 at 20:41
• Good answer btw; I'll award the bounty as soon as it will allow. I have posted a question here asking for some $k$ such that every $k$-dense graph has strictly more than $2^{k+1}-1$ vertices. Feb 19, 2019 at 21:10