Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $D$ be some directed graph, and let $G$ and $G'$ be two acyclic subgraphs of $D$; let $E$ and $E'$ be their sets of edges. Is it possible to give a simple criterion on $E$ and $E'$ (sufficiency and necessity would be great, of course) for when the subgraph given by $E \cup E'$ is still acyclic?

(I can come up with [fairly trivial] necessary conditions, and also with [fairly elaborate] sufficient conditions, but all these are far from optimal.)

Thanks!

Edit: changed the wording and the title in response to Qiaochu Yuan's comments.

share|improve this question
1  
The union is always a DAG. –  Qiaochu Yuan Feb 17 '12 at 5:45
    
@QiaochuYuan: If $V = V' = \{a, b\}, E = \{(a, b)\}, E' = \{(b, a)\}$, then $(V, E)$ and $(V', E')$ are both acyclic, but $(V\cup V' = V, E \cup E' = \{(a, b), (b, a)\})$ is not acyclic. –  kjo Feb 17 '12 at 5:51
3  
I suspect that no better criterion can be given than "$E\cup E'$ contains no cycles." Just out of curiosity, can I ask why you are interested in the union operation on DAGs? –  Alex Kruckman Feb 17 '12 at 5:55
1  
Oh, I didn't realize you weren't assuming that $V, V'$ are disjoint. I don't think it is good practice to call this operation the union of two DAGs. I would prefer that you call it the union of two sub-DAGs of some graph. (For me the union of two sets is either the disjoint union or it is only defined for subsets of a set. I don't like the union in the ZFC sense.) –  Qiaochu Yuan Feb 17 '12 at 6:31
    
@AlexKruckman: I'm learning about posets, and I wanted to understand better when the transitive closure of the union of two partial orders on the same underlying set is still antisymmetric. This question, in turn, arises from a looking at the partial orders induced on a set $Y$ by a partial order on some other set $X$ and two functions $X\to Y$. –  kjo Feb 17 '12 at 14:15

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.