A numbering of the vertices of special networks

✍ Scribed by H. Fleischner

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 912 KB
• Volume: 165-166
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(96)00176-8

✦ Synopsis

We characterize acyclic digraphs which remain acyclic under a certain type of arc addition. The vertices of such digraphs D admit a labelling f such that f(x) < f(y) and f(x) = ,f(z) whenever (x, y) and (x,z) are arcs of D. The study of such digraphs has been initiated by a software development problem.