I call a digraph G= (V,E) essentially interconnected if whenever any vertex $a$ is removed from $G$ there is always at least one pair of distinct vertices $v$ and $w$ which can no longer be joined by an oriented path in $G$.
Are there essentially interconnected graphs ?
Example: The cycle: (a,b), (b,c),(c,a)
If I remove $b$ then I cannot connect $a$ to $c$ (although I can connected $c$ to $a$) and analogusly for $a$ and $c$.
Can we characterise such digraphs in general ?
Hi. Are you allowing for bidirected edges or for the graph to be a directed multigraph? Regardless, I think that your digraph has to be strongly connected.
These are the relevant definitions:
A directed graph is called weakly connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph. It is unilaterally connected or unilateral (also called semiconnected) if it contains a directed path from u to v or a directed path from v to u for every pair of vertices u, v.[2] It is strongly connected, or simply strong, if it contains a directed path from u to v and a directed path from v to u for every pair of vertices u, v.
A vertex cut or separating set of a connected graph G is a set of vertices whose removal renders G disconnected. The vertex connectivity κ(G) (where G is not a complete graph) is the size of a minimal vertex cut. A graph is called k-vertex-connected or k-connected if its vertex connectivity is k or greater.
According to your description, we are assuming that the graph G is initially strongly connected. Otherwise, there are already vertices that are not reachable from at least one other vertex via a directed path. Removal of one vertex causes G to become weakly connected. None of the descriptions above fits this. But we can probably say it is 1-vertex-weakly connected, which means removing one vertex makes the graph weakly connected.
I would rephrase my definition more clearly:
A graph G = (V,E) is essentially interconnected if for every v in V, if we consider the graph G' that results from removing v from G, then there are two distinct vertices a and b (different from v) which can be connected by a directed path from a to b in G but not by a directed path from a to b in G'.
An essentially interconnected graph is certainly weakly connected.
My example of a cycle is indeed strongly connected.
All examples of essentially interconnected graphs I can think of are strongly connected.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs