4
$\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?)

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ I guess you're talking only about finite directed acyclic graphs? $\endgroup$
    – Joel David Hamkins
    Commented Jun 16, 2013 at 3:31
  • $\begingroup$ @Joel: Yes I was only thinking about finite DAGs. $\endgroup$
    – Aeryk
    Commented 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$
    – Joel David Hamkins
    Commented Jun 16, 2013 at 4:11
  • 1
    $\begingroup$ Or, "non-empty well-orderable graphs with no infinite directed paths". $\;$ $\endgroup$
    – user5810
    Commented 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$
    – Theo Johnson-Freyd
    Commented Jun 18, 2013 at 2:32

3 Answers 3

Reset to default
6
$\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).

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Urgh. That's an ugly name :-/ $\endgroup$
    – Mariano Suárez-Álvarez
    Commented 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$
    – Joseph O'Rourke
    Commented Jun 16, 2013 at 5:39
  • $\begingroup$ "st-DAG" = "source-target DAG" $\endgroup$
    – Steve Huntsman
    Commented 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.

Improve this answer
$\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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .