Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
1  
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
2  
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
1  
Or, "non-empty well-orderable graphs with no infinite directed paths". $\;$ –  Ricky Demer Jun 16 '13 at 21:38

2 Answers 2

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

share|improve this answer
1  
Urgh. That's an ugly name :-/ –  Mariano Suárez-Alvarez Jun 16 '13 at 4:47
1  
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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