# Term for “Directed acyclic graph with exactly one sink and one source”

There's a theorem/lemma that states that a finite directed acyclic graph (DAG) has at least one sink and at least one source. Is there a term for a (finite) DAG with exactly one sink and one source?

(And while you're at it, any good background references for someone whose research just took a left turn into such DAGs?)

-
I guess you're talking only about finite directed acyclic graphs? –  Joel David Hamkins Jun 16 '13 at 3:31
@Joel: Yes I was only thinking about finite DAGs. –  Aeryk Jun 16 '13 at 3:36
Aeryk, you can edit to change your first sentence to add the finiteness hypothesis, since it isn't true for all directed acyclic graphs. For example, the integers under the successor relation is a DAG with no sources or sinks. –  Joel David Hamkins Jun 16 '13 at 3:51
And I guess (please excuse this trivial remark) one needs to say "nonempty" as well, since the empty graph is directed and acyclic, but has no sources or sinks. –  Joel David Hamkins Jun 16 '13 at 4:11
Or, "non-empty well-orderable graphs with no infinite directed paths". $\;$ –  Ricky Demer Jun 16 '13 at 21:38

In Fully Dynamic Transitive Closure in Plane Dags with One Source and One Sink (1994) by Thore Husfeldt this is called a source-sink graph (or short st-graph) by Definition (1).

-
Urgh. That's an ugly name :-/ –  Mariano Suárez-Alvarez Jun 16 '13 at 4:47
The term st-graph is well-established in the literature for over twenty years (e.g., Tamassia's "Drawing algorithms for planar st-graphs," 1990). Maybe because I'm accustomed to it, I find "st-graph" natural. –  Joseph O'Rourke Jun 16 '13 at 5:39
"st-DAG" = "source-target DAG" –  Steve Huntsman Jun 17 '13 at 17:32

I have seen the term "interval" used for this notion, at least in the context of subgraphs of a larger DAG. I'm not saying it's a good term, just that I've seen it used.

-