From the 1 of 27 linked papers with an AI index.
13 papers · 1 filter
Minimum degree conditions for graph rigidity
Michael Krivelevich, Alan Lew, Peleg Michaeli
We study minimum degree conditions that guarantee that an -vertex graph is rigid in . For small values of , we obtain a tight bound: for , ever…
Fast construction on a restricted budget
Alan Frieze, Michael Krivelevich, Peleg Michaeli
We introduce a model of a controlled random graph process. In this model, the edges of the complete graph are ordered randomly and then revealed, one by one, to a player call…
Disjoint connected dominating sets in pseudorandom graphs
Nemanja DraganiÄ, Michael Krivelevich
A connected dominating set (CDS) in a graph is a dominating set of vertices that induces a connected subgraph. Having many disjoint CDSs in a graph can be considered as a measure o…
Components, large and small, are as they should be II: supercritical percolation on regular graphs of constant degree
Sahar Diskin, Michael Krivelevich
Let be a fixed integer. Let be the probability that the root of an infinite -regular tree belongs to an infinite cluster after -bond-percolation. We show…
Reconstructing random graphs from distance queries
Michael Krivelevich, Maksim Zhukovskii
We estimate the minimum number of distance queries that is sufficient to reconstruct the binomial random graph with constant diameter with high probability. We get a tight…
Large matchings and nearly spanning, nearly regular subgraphs of random subgraphs
Sahar Diskin, Joshua Erde, Mihyun Kang +1
Given a graph and , the random subgraph is obtained by retaining each edge of independently with probability . We show that for every , there exi…