Take the 2-minute tour ×

What's the name for a digraph such that for each pair of vertices $u,v$, there is either a path from $u$ to $v$ or a path from $v$ to $u$? I'd call it just connected, since this is an intermediate property between weak and strong connectivity, and is in fact equivalent to the existence of a path containing all vertices. However, I'm not an expert of the subject, and I was unable to find any reference about this, so far.

share|improve this question

4 Answers 4

up vote 4 down vote accepted

Just `connected' is fine. For example, Wikipedia and Tutte agree. However, since "the number of systems of terminology presently used in graph theory is equal, to a close approximation, to the number of graph theorists," (R.P. Stanley, 1986) you might want to include the definition anyway.

share|improve this answer
Thank you! I had not seen the definition on Wikipedia. It was added by an anonymous user on last Oct 13, apparently. I had asked the same question in the talk page, but nobody answered me there. The reference from Tutte is completely satisfactory for me. –  Ale De Luca Jul 5 '10 at 18:13

Another term that has been used is "unilateral" or "unilaterally connected". I don't have a particularly strong opinion in favor of this terminology, but I am slightly opposed to just calling it "connected". (I usually assume "connected" means "weakly connected" for digraphs.) However, I must admit a reference by Tutte is good.

Some references for "unilateral":

share|improve this answer
thank you very much! –  Ale De Luca Jul 7 '10 at 17:16

Such digraph is called traceable. For example, it is defined as such in the paper http://www.ams.org/bull/1976-82-01/S0002-9904-1976-13955-9/S0002-9904-1976-13955-9.pdf

share|improve this answer
Thank you very much for your answer. It seems, however, that the definition of traceable graph in such paper requires the existence of a Hamiltonian path. This is not equivalent to what I am asking; I am not interested whether the path visits each vertex exactly once, as long as it does visit all of them. For example, the digraph $\{(a,b),(b,a),(a,c),(c,a),(a,d)\}$ is "connected" as I'm meaning, but it is not traceable as the shortest path visiting all vertices is $bacad$ (or $cabad$), thus visiting $a$ twice. The same graph is also not strongly connected, as no edge starts from $d$. –  Ale De Luca Jul 5 '10 at 0:29

Such a graph is called a semiconnected graph. You can find references to it in Cormen and Diestel's book on graph theory http://diestel-graph-theory.com/

share|improve this answer
Thanks… but again, it doesn't quite seem to be the same thing. In Diestel's book I could only find a definition for semiconnectedness of submultigraphs of infinite graphs. It is not obvious to me how would this apply to digraphs in general. –  Ale De Luca Jul 5 '10 at 18:10

Your Answer


