125 citations · 357 across the 38 of their papers we have counts for
47 papers
On the Connectivity and Diameter of Geodetic Graphs
Asaf Etgar, Nati Linial
A graph is geodetic if between any two vertices there exists a unique shortest path. In 1962 Ore raised the challenge to characterize geodetic graphs, but despite many attempts…
Bounds on Unique-Neighbor Codes
Nati Linial, Edan Orzech
Recall that a binary linear code of length is a linear subspace . Here the parity check matrix is a binary matrix…
Irreducible Non-Metrizable Path Systems in Graphs
Daniel Cizma, Nati Linial
A path system in a graph is said to be irreducible if there does not exist a partition such that restricts to a path system on…
A randomized construction of high girth regular graphs
Nati Linial, Michael Simkin
We describe a new random greedy algorithm for generating regular graphs of high girth: Let and be fixed. Let be even and set $g = c \log_…
A King in every two consecutive tournaments
Yehuda Afek, Eli Gafni, Nati Linial
We think of a tournament as a communication network where in each round of communication processor sends its information to , for every directed edge $ij \i…
On the local structure of oriented graphs -- a case study in flag algebras
Shoni Gilboa, Roman Glebov, Dan Hefetz +2
Let be an -vertex oriented graph. Let (respectively ) be the probability that a random set of vertices of spans a transitive triangle (respectively an i…