views:

36

answers:

1

Is there a term to describe a graph who has only one subgraph that is strongly connected? (I'm not even sure I'm using strongly connected correctly here).

eg. {AB,BC} has only one subgraph and {AB,BC,DE} has two.

Note that I'm not considering that the graph {AB,BC} has three subgraphs: {AB,BC} and {AB} and {BC}.

please distinguish between undirected and directed if need be.

+1  A: 

I think you mean a connected graph, the alternative being a forest disconnected graph.

From http://en.wikipedia.org/wiki/Connectivity_%28graph_theory%29 --

A graph is called connected if every pair of distinct vertices in the graph can be connected through some path. A directed graph is called weakly connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph. It is connected 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. It is strongly connected or 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. The strong components are the maximal strongly connected subgraphs.

Joel
connected seems correct. But forest doesn't seem to be the alternative. From wiki: "In other words, any connected graph without cycles is a tree. A forest is a disjoint union of trees." I am consider cycles so connected is correct and forest is not. I think "disjoint union of connected graphs" may be the alternative.
harschware
You are correct. Edited in post.
Joel