## Digraph intermediate connectivity

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

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.

-

## 4 Answers

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.

-

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

### 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.

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

-

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

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/

-

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

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)
-

thank you very much! – Ale De Luca Jul 7 2010 at 17:16
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 10, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9630988836288452, "perplexity_flag": "middle"}