On the relationship between the diameter and the size of a boundary of a directed graph

DOI10.1016/0020-0190(94)00044-1zbMath0799.05024OpenAlexW2023168082MaRDI QIDQ1329425

Akira Maruoka, Shuji Jimbo

Publication date: 4 July 1994

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)00044-1

zbMATH Keywords

digraphdiameterlower boundboundary

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20)

Cites Work

• Unnamed Item
• Sorting in \(c \log n\) parallel steps
• Expanders obtained from affine transformations
• Ramanujan graphs
• Eigenvalues and expanders
• Asymptotically optimal switching circuits
• Explicit constructions of linear-sized superconcentrators
• Limitations on Explicit Constructions of Expanding Graphs
• Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines
• Better expanders and superconcentrators

This page was built for publication: On the relationship between the diameter and the size of a boundary of a directed graph