Welcome to MathOverflow

Question

2

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.

edited Jul 7 2010 at 17:50

asked Jul 4 2010 at 16:51

Ale De Luca
132●1●8

rgrig · Accepted Answer · 2010-07-05 12:08:10Z UTC

4

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.

answered Jul 5 2010 at 12:08

rgrig
531●7●12

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 2010 at 18:13

aorq · Answer 2 · 2010-07-07 03:34:52Z UTC

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)

Max Alekseyev · Answer 3 · 2010-07-04 21:09:27Z UTC

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

edited Jul 4 2010 at 21:09

answered Jul 4 2010 at 20:59

Max Alekseyev
1,669●4●9

2

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 2010 at 0:29

Akhil Ravidas · Answer 4 · 2010-07-05 06:13:38Z UTC

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/

answered Jul 5 2010 at 6:13

Akhil Ravidas
11●1

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 2010 at 18:10

Digraph intermediate connectivity

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

4 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.