5
$\begingroup$

As far as I know, it is an unsolved question whether or not this is true:

If $G$ is a directed an oriented graph, $G^2$ always has some node whose outdegree is at least double that of its outdegree in $G$.

For example, below vertex $10$ has outdegree $3$ in $G$ and $5$ in $G^2$. The maximum outdegree-ratio increase of $3.5$ is achieved by vertex $15$, which has outdegree $2$ in $G$ and $7$ in $G^2$. Of course there are also vertices, such as $2$ in $G$, that have zero-outdegree, and so their outdegree trivially doubles and satisfies the above hypothesis.


          GdirSq15
          A directed graph $G$ on $n=15$ nodes; and $G^2$.


My question is:

Q. Is the expected maximum (finite) outdegree increase from $G$ to $G^2$ known to grow logarithmically in $n$, for random directed graphs generated by including each of the $2\binom{n}{2}$ directed edges with fixed probability $p$?

Simulations suggest this may be true:


          SqDirGraph
          The maximum (finite) outdegree ratio increase, for $n$-node random graphs, each edge included with probability 3%.
          Each point is an average of $5$ simulations. The illustrated curve is logarithmic.


$\endgroup$
  • $\begingroup$ The link refers to oriented graphs, not directed graphs, and also implies that multiple edges are suppressed in forming $G^2$. Is that true for you too? $\endgroup$ – Brendan McKay Jul 25 '15 at 0:45
  • $\begingroup$ @BrendanMcKay: Good point. I used directed random graphs with no loops or multiple edges for $G$, but allowed $G^2$ to be whatever was dictated by squaring. $\endgroup$ – Joseph O'Rourke Jul 25 '15 at 0:48
  • 3
    $\begingroup$ On your second question, for fixed $p$ asymptotically $G^2$ is a complete graph. To make the question interesting you need to have $p$ decrease as $n$ increases. But it still looks like a pretty standard random graph problem. $\endgroup$ – Brendan McKay Jul 25 '15 at 1:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.