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, 2013 at 3:31
  • $\begingroup$ @Joel: Yes I was only thinking about finite DAGs. $\endgroup$
    – Aeryk
    Jun 16, 2013 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, 2013 at 4:11
  • 1
    $\begingroup$ Or, "non-empty well-orderable graphs with no infinite directed paths". $\;$ $\endgroup$
    – user5810
    Jun 16, 2013 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, 2013 at 2:32

3 Answers 3

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, 2013 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, 2013 at 5:39
  • $\begingroup$ "st-DAG" = "source-target DAG" $\endgroup$ Jun 17, 2013 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 and acknowledge you have read our privacy policy.

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