30
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Am I missing something, or is the fact that your graphs are directed irrelevant? $\endgroup$ Aug 11, 2016 at 12:27
  • $\begingroup$ 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$... $\endgroup$ Aug 11, 2016 at 14:25
  • 2
    $\begingroup$ 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. $\endgroup$
    – Jal
    Aug 13, 2016 at 18:10
  • $\begingroup$ Is it even clear that your greedy algorithm produces the smallest number of nodes? $\endgroup$
    – Tad
    Aug 14, 2016 at 1:44
  • $\begingroup$ @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$. $\endgroup$ Aug 14, 2016 at 21:24

1 Answer 1

6
+50
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Feb 19, 2019 at 20:41
  • $\begingroup$ 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. $\endgroup$ Feb 19, 2019 at 21:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .