Shallow grates (Q1314391)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Shallow grates |
scientific article; zbMATH DE number 501199
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Shallow grates |
scientific article; zbMATH DE number 501199 |
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
0 references
0 references
0.69625545
0 references
