Digraph intermediate connectivity - MathOverflow

Digraph intermediate connectivity

2010-07-04T16:51:32Z

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.

Answer by Max Alekseyev for Digraph intermediate connectivity

2010-07-04T20:59:34Z

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

Answer by Akhil Ravidas for Digraph intermediate connectivity

2010-07-05T06:13:38Z

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/

Answer by rgrig for Digraph intermediate connectivity

2010-07-05T12:08:10Z

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.

Answer by aorq for Digraph intermediate connectivity

2010-07-07T03:34:52Z

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)