A numbering of the vertices of special networks (Q1356750): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q592071 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Wai-Kai Chen / rank | |||
Normal rank |
Revision as of 05:11, 20 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A numbering of the vertices of special networks |
scientific article |
Statements
A numbering of the vertices of special networks (English)
0 references
7 October 1997
0 references
The paper characterizes acyclic digraphs which remain acyclic under a certain type of arc addition. The vertices of such digraphs admit a labelling \(f\) such that \(f(x)< f(y)\) and \(f(x)= f(z)\) whenever \((x,y)\) and \((x,z)\) are arcs of the digraph. The characterization is via a unique forbidden subgraph, which yields an acyclic digraph under a certain closure operation. The paper also develops an algorithm for constructing such functions.
0 references
acyclic digraphs
0 references