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.
$\begingroup$
$\endgroup$
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
1
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.
-
$\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$ Commented Jul 5, 2010 at 18:13
$\begingroup$
$\endgroup$
0
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":
- Graph theory applications by L. R. Foulds
- On minimal feedback vertex sets of a digraph by Frank Harary (I think Harary's graph theory book uses it also)
$\begingroup$
$\endgroup$
1
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
answered Jul 4, 2010 at 20:59
-
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$ Commented Jul 5, 2010 at 0:29
$\begingroup$
$\endgroup$
1
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/
-
$\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$ Commented Jul 5, 2010 at 18:10