18
$\begingroup$

A unipathic graph is a directed graph such that there is at most one simple path from any one vertex to any other vertex.

Unipathic graphs can have cycles. For example, a doubly linked list (not a circular one!) is a unipathic graph; if the list has $n$ elements, the graph has $n-1$ cycles of length 2, for a total of $2(n-1)$.

What is the maximum number of edges in a unipathic graph with $n$ vertices? An asymptotic bound would do (e.g. $O(n)$ or $\Theta(n^2)$).

Inspired by Find shortest paths in a weighed unipathic graph; in my proof, I initially wanted to claim that the number of edges was $O(n)$ but then realized that bounding the number of cycles was sufficient.

$\endgroup$
  • $\begingroup$ Nice question. We should try to improve either your lower bound or my upper bound :). $\endgroup$ – R B Jan 15 '15 at 0:20
12
$\begingroup$

A unipathic graph can have $\Theta(n^2)$ edges. There's a well-known kind of graph that's unipathic and has $n^2/4$ edges.

Consider a complete bipartite graph, with oriented edges $\forall (i,j) \in [1,m]^2, a_i \rightarrow b_j$. This graph is unipathic and has no cycle: all its paths have length $1$. It has $2m$ vertices and $m^2$ edges.

(Follow-up question: is this ratio maximal? Probably not, but I don't have another example. This example is maximal in the sense that any one edge that you add between existing nodes will break the unipathic property.)

$\endgroup$
  • $\begingroup$ "any one edge that you add between existing nodes will break the unipathic property" How would adding the edge $b_1 \rightarrow a_1$ break the property? $\endgroup$ – mitchus Mar 23 '12 at 14:05
  • $\begingroup$ @mitchus $a_2 \rightarrow b_1 \rightarrow a_1 \rightarrow b_2$ $\endgroup$ – Gilles Mar 23 '12 at 16:42
  • 1
    $\begingroup$ I guess my mind was somehow unipathic that day :) As for maximality, the ratio may go to 1/4 for large $n$, but for $n \in \{2,3,4,5,6\}$ the doubly linked list has more edges than $n^2/4$. $\endgroup$ – mitchus Mar 26 '12 at 11:02
0
$\begingroup$

I don't know if there a unipathic graph on more than $\frac{n^2}{4}$ edges, but here's an argument showing that no more than $\frac{n^2}{2}+3$ edges are possible:

Assume by contradiction that $G=(V,E)$ is a unipathic graph such that $|E|\geq \frac{n^2}{2}+3$.

By the pigeonhole principle, there exist $v\in V$ such that $$d_{\text{in}}(v)\geq \frac{n}{2}+1$$

Denote $U=\{u\in V\mid (u,v)\in E\}$

Notice that if there was a vertex $x\in V\setminus \{v\}$ such that $$\exists u_1\neq u_2\in U:(x,u_1),(x,u_2)\in E$$

Then the graph wouldn't be unipathic (as $(x\to u_1\to v)$ and $(x\to u_2\to v)$ are both valid paths).

This means that (adding the edges from $\{v\}\times U$): $$|E\cap (V\times U)|\leq2|U|$$

So the average in-degree of $U$'s vertices is at most 2, hence: $$|E|=|E\cap (V\times U)|+|E\cap (V\times (V\setminus U))|$$ $$\leq 2|U|+n|V\setminus U|\leq 2(\frac{n}{2}+1)+n(\frac{n}{2}-1)<\frac{n^2}{2}+3$$

$\square$

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.