<p>Let <span class="math-container">$G$</span> be a directed graph without loops (or even better an oriented graph). Let us assume that <span class="math-container">$G$</span> is finite.
The graph <span class="math-container">$G$</span> is <em>connected</em> if its underlying graph <span class="math-container">$G^*$</span> is connected (i.e., for every pair of vertices <span class="math-container">$u$</span> and <span class="math-container">$v$</span> in <span class="math-container">$G^*$</span>, there is a <span class="math-container">$u,v$</span>-path in <span class="math-container">$G^*$</span>). The graph <span class="math-container">$G$</span> is <em>strongly connected</em> if for every pair of vertices <span class="math-container">$u$</span> and <span class="math-container">$v$</span> in <span class="math-container">$G$</span>, there is a directed <span class="math-container">$u,v$</span>-path in <span class="math-container">$G$</span>.</p>
<p><strong>Is there a notion between 'connected' and 'strongly connected'?</strong><br />
For the specific purpose I had in mind for oriented graphs, every &quot;intermediate&quot; notion I came up with turned out be equivalent to strongly connectedness.</p>
<p>I would also be interested in an intermediate notion for mixed graphs <span class="math-container">$G$</span> (i.e. graphs where there are some arcs and some undirected edges), provided the new notion indeed reflect a connectivity property of <span class="math-container">$G$</span>.</p>
<p>e.g.: One notion that is intermediate between connected and strongly connected is 'unilaterally connected'.<br />
A directed graph <span class="math-container">$G$</span> is <em>unilaterally connected</em> if for any two vertices <span class="math-container">$u$</span> and <span class="math-container">$v$</span>, there is a directed path from <span class="math-container">$u$</span> to <span class="math-container">$v$</span> or from <span class="math-container">$v$</span> to <span class="math-container">$u$</span> but not necessarily both.</p>
<p>Please post one notion per answer (mentioning generalisations in one answer is acceptable and appreciated).</p>

CC BY-SA 4.0
2023-06-30T03:23:39.107Z
What about counting the number of back-edges on u-v paths? Say that G is i-connected if between every pair of vertices there’s a path with at most i back edges?
daniello
CC BY-SA 4.0
2023-06-30T03:47:39.047Z
@daniello Sorry, I don't understand what you meant by back edges. Are you assuming a DFS representation of the graph and talking about back edges in that DFS tree?
Cyriac Antony
CC BY-SA 4.0
2023-06-30T14:12:42.677Z
What I mean is allowing at most i edges to go in the wrong direction in the definition of a u-v path.
daniello
CC BY-SA 4.0
2023-07-01T04:05:58.117Z
@daniello That's interesting. Please post it as an answer.
Cyriac Antony
<graph-theory>
Notion between connected and strongly connected graphs
Cyriac Antony
# Notion between connected and strongly connected graphs

(Asked by: username_0 on 2023-06-30)

Let $G$ be a directed graph without loops (or even better an oriented graph). Let us assume that $G$ is finite.
The graph $G$ is *connected* if its underlying graph $G^\*$ is connected (i.e., for every pair of vertices $u$ and $v$ in $G^\*$, there is a $u,v$-path in $G^\*$). The graph $G$ is *strongly connected* if for every pair of vertices $u$ and $v$ in $G$, there is a directed $u,v$-path in $G$.

**Is there a notion between 'connected' and 'strongly connected'?**  
For the specific purpose I had in mind for oriented graphs, every "intermediate" notion I came up with turned out be equivalent to strongly connectedness.

I would also be interested in an intermediate notion for mixed graphs $G$ (i.e. graphs where there are some arcs and some undirected edges), provided the new notion indeed reflect a connectivity property of $G$.

e.g.: One notion that is intermediate between connected and strongly connected is 'unilaterally connected'.  
A directed graph $G$ is *unilaterally connected* if for any two vertices $u$ and $v$, there is a directed path from $u$ to $v$ or from $v$ to $u$ but not necessarily both.

Please post one notion per answer (mentioning generalisations in one answer is acceptable and appreciated).

**Tags:** graph-theory
> **Comments:**
> **username_1**: What about counting the number of back-edges on u-v paths? Say that G is i-connected if between every pair of vertices there’s a path with at most i back edges?  
> **username_0**: @daniello Sorry, I don't understand what you meant by back edges. Are you assuming a DFS representation of the graph and talking about back edges in that DFS tree?  
> **username_1**: What I mean is allowing at most i edges to go in the wrong direction in the definition of a u-v path.  
> **username_0**: @daniello That's interesting. Please post it as an answer.  

---

## 0 answers

