3
$\begingroup$

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

$\endgroup$
6
  • 1
    $\begingroup$ I guess you're talking only about finite directed acyclic graphs? $\endgroup$ Jun 16 '13 at 3:31
  • $\begingroup$ @Joel: Yes I was only thinking about finite DAGs. $\endgroup$
    – Aeryk
    Jun 16 '13 at 3:36
  • 3
    $\begingroup$ 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. $\endgroup$ Jun 16 '13 at 4:11
  • 1
    $\begingroup$ Or, "non-empty well-orderable graphs with no infinite directed paths". $\;$ $\endgroup$
    – user5810
    Jun 16 '13 at 21:38
  • 1
    $\begingroup$ @JDH: A better statement than adding "nonempty" near the beginning would be to add "in each component" at the end. This gives generically a stronger statement than the one OP started with, and covers the $\emptyset$ case as well. $\endgroup$ Jun 18 '13 at 2:32
5
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ Urgh. That's an ugly name :-/ $\endgroup$ Jun 16 '13 at 4:47
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 16 '13 at 5:39
  • $\begingroup$ "st-DAG" = "source-target DAG" $\endgroup$ Jun 17 '13 at 17:32
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

Besides the previously mentioned st-dag or st-DAG (source-target DAG) the term "two-terminal directed acyclic graph" is also often used.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.