2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Jul 5 '10 at 18:13
2
$\begingroup$

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":

$\endgroup$
0
1
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ 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$. $\endgroup$ Jul 5 '10 at 0:29
1
$\begingroup$

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/

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Jul 5 '10 at 18:10

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.