9
$\begingroup$

Let $G$ be a directed graph.

Call a vertex $v$ in $G$ central if there exists $\Theta(n^2)$ distinct pairs of vertices $(u,w)$ such that $v$ lies on some path from $u$ to $w$. We do not care whether these paths are shortest or not, nor whether other paths avoiding $v$ exist.

Question: Do strongly connected digraphs always admit a central vertex?

Improve this question
$\endgroup$
14
  • $\begingroup$ I'm confused about a few things here. First, what do you mean by Theta(n) for a specific graph? Is the idea that you want a constant C so that there is a vertex part of at least Cn^2 such paths for all strongly connected digraphs? (Also, I assume n is the number of vertices?) Also, I would say that every vertex is central for a silly reason: by strong connectedness, for all u,v,w, there is a path from u to v and a path from v to w, so v is on a path from u to w. Can you clarify? $\endgroup$
    – Ronnie Pavlov
    Commented Mar 8, 2023 at 18:45
  • 1
    $\begingroup$ Yes, $n$ is the number of vertices. By $\Theta(n^2)$, I am asking if there exists a constant $c$ such that in every strongly connected digraph, at least one vertex lies on a path between $c\cdot n^2$ pairs of vertices. Note that I want a path here, not a walk, i.e. one that cannot visit intermediate vertices twice (otherwise, I would agree with your objection). Perhaps I should have said "self-avoiding path" to avoid this ambiguity. Thanks for asking for these clarifications! $\endgroup$
    – Arnaud Casteigts
    Commented Mar 8, 2023 at 19:29
  • $\begingroup$ Ahhhh, OK. Thanks! $\endgroup$
    – Ronnie Pavlov
    Commented Mar 8, 2023 at 21:16
  • 1
    $\begingroup$ Unfortunately, you didn't get the answer you were looking for, but I'd just like to point out that the most promising direction to me is the one pointed out by @TimothyChow (my "answer" was weakened by the thing I pointed out in the addendum). That is, to focus on minimal strongly connected digraphs. These are much more complicated than trees, but there are some nice structural results here doi.org/10.1016/j.laa.2017.11.027 which could be helpful. For instance what additional structural properties can be proved under the assumption that there are no paths of length $\Theta(n)$? $\endgroup$
    – Louis D
    Commented Mar 15, 2023 at 15:51
  • 1
    $\begingroup$ @ArnaudCasteigts Oh sorry about that. The approach I had was actually fatally flawed in a number of ways, to the point it was not repairable. Fundamentally, I believed that one of the maximal vertices in one of the Hasse diagrams in the decomposition would have to be one of these central vertices but it is actually not the case. I have a counter-example that I can post as an answer if you're curious. $\endgroup$
    – mhum
    Commented Mar 29, 2023 at 18:47

2 Answers 2

Reset to default
5
$\begingroup$

In this manuscript, Bessy, Thomassé, and Viennot proved the following stronger property:

Let $D$ be a strongly connected directed graph, then there is a vertex $v$ in $D$ such that there exists an in-tree towards $v$ and an out-tree from $v$ that are vertex-disjoint (apart from sharing $v$ itself) and contain at least $n/6$ vertices each.

As a result, $v$ lies on a path between at least $n^2/36$ pairs of vertices.

Improve this answer
$\endgroup$
2
+50
$\begingroup$

I don't have an answer, but I do have an idea for how a proof could go. I would make this a comment, but it is too long.

(i) Prove that every 2-strongly connected digraph (i.e. remains strongly connected after the deletion of any vertex, or equivalently, by Menger's theorem, for every pair of vertices x,y, there are two internally disjoint x,y-paths and two internally disjoint y,x-paths) has the property that for every ordered triple of vertices u,v,w there is a uw-path that contains v.
(For graphs, this is a standard application of Menger's theorem, but the same proof doesn't seem to hold for digraphs.)

BEGIN ADDENDUM: The reason I couldn't see how to prove (i) is because it is not true. See the figure on page 2 of "About Some Cyclic Properties in Digraphs" by Heydemann and Sotteau. They refer to the property that for every ordered triple of vertices u,v,w there is a uw-path that contains v as "property (T)". They point out that Thomassen proved (Theorem 2 in "Highly connected non-2-linked digraphs") that for every k, there is a k-strongly connected digraph having the property that there are 2-vertices which are non contained together in a cycle and thus property (T) fails.

Of course, this doesn't rule out proving that in a 2-strongly connected digraph on n vertices there is a central vertex, but perhaps even this will be challenging to prove.

I suppose the only takeaway from all of this is that you can at least focus on proving your conjecture for 2-strongly connected digraphs.

END ADDENDUM

(ii) For undirected graphs there is the concept of a block-cut tree (https://en.wikipedia.org/wiki/Biconnected_component). Basically, this allows you to partition the graph into 2-connected "components" keeping track of the connections between those components. I don't know the definitive reference for the analogous concept in digraphs, but this paper might be it ("Strong k-connectivity in digraphs and random digraphs" by Reif and Spirakis)

(iii) Every vertex weighted tree T with weights between 0 and 1/2 and summing to 1 over all vertices has the property that there is a vertex v such that every component of T-v has weight at most 1/2 (the unweighted version is a well-known fact https://math.stackexchange.com/questions/1742440/you-can-always-delete-a-vertex-from-a-tree-g-such-that-the-remaining-connected and the weighted version has basically the same proof).

(iv) Now either there is a 2-strongly connected subdigraph with $\Theta(n)$ vertices and we are done by (i), or every 2-strongly connected subdigraph has order o(n) and then use (ii) and (iii) to get the desired central vertex.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Interesting! Yes, the T property is stronger than what we want to achieve. It could be worth investigating further in [HS] where the T property breaks in 2-connected digraphs, and see if a "central" vertex still exists in that case. (I will do it eventually if there are no other definite answer.) $\endgroup$
    – Arnaud Casteigts
    Commented Mar 13, 2023 at 9:32

You must log in to answer this question.

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