Distance pairs in labeled directed graph

Question

Suppose we have a simple directed graph with $n$ nodes and $m$ edges, and we label each edge from $1$ to $m$ (with distinct labels). Define the weighted "length" of a directed path to be the maximum of all edge labels on that path (or $0$ for a trivial path), and define the "distance" $d(a, b)$ from node $a$ to $b$ to be the minimum weight of all paths from $a$ to $b$ (or $\infty$ if $b$ is not reachable from $a$).

Define a triple $a, b, c$ of nodes to be defective if $d(a, c) < d(a, b) < \infty$ and $d(b, c) < d(a, b)$.

I have two questions:

A) What is the maximum number of defective triples possible?

B) What is the average number of defective triples if edge labels are assigned at random?

Unfortunately, I haven't been able to make much progress on either one, so I was hoping other people might have insight into the problem.

Answer 1

For A), here is a construction that gives $2\binom{n}{3}$ defective triples, which is almost best possible. Let $D$ be a digraph with vertex set $[n]$ and arcs $(i,i+1)$ and $(i+1, i)$ for all $i \in [n-1]$. Let the label of the arc $(i,i+1)$ be $n-1+i$, and the label of the arc $(i+1, i)$ be $i$.

For all $i<j<k$, I claim that $(i,k,j)$ is a defective triple. To see this, note that $d(i,j)=n+j-2 < n+k-2=d(i,k)$ and $d(k,j)=k-1 < n+k-2=d(i,k)$.
Similarly, $(j,k,i)$ is also a defective triple.

Thus, this example contains $2\binom{n}{3}$ defective triples.

In general, note that if $(a,b,c)$ is a defective triple, then $(a,c,b)$ cannot be a defective triple. Thus, every digraph on $n$ vertices contains at most $3 \binom{n}{3}$ defective triples, so our bound is tight up to a factor of $\frac{3}{2}$.