A numbering of the vertices of special networks (Q1356750): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q3856672 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Eulerian graphs and related topics. Part 1, Volume 1 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Eulerian graphs and related topics. Part 1, Volume 2 / rank | |||
Normal rank |
Latest revision as of 14:13, 27 May 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