Shallow grates (Q1314391)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Shallow grates |
scientific article |
Statements
Shallow grates (English)
0 references
22 February 1994
0 references
This note gives a construction for a family of weak grates; that is, acyclic digraphs of logarithmic depth with this property: A superlinear number of pairs of vertices remain connected after removing any sufficiently small linear sized vertex set. The construction is based on one by Schnitger for acyclic digraphs with a similar property. Schnitger's graphs are modified by replacing vertices and edges by appropriate vertex sets and edge sets. The construction easily generalizes to digraphs of arbitrary depth.
0 references
grates
0 references
acyclic digraphs
0 references
Schnitger's graphs
0 references
