94 citations · 100 across the 9 of their papers we have counts for
9 papers
High degree graphs contain large-star factors
Noga Alon, Nicholas Wormald
We show that any finite simple graph with minimum degree contains a spanning star forest in which every connected component is of size at least . This sett…
Economical toric spines via Cheeger's Inequality
Noga Alon, Bo'az Klartag
Let denote the graph whose set of vertices is , where two distinct vertices are adjacent iff they are either equal or adjacent in $C_m…
Broadcasting with side information
Noga Alon, Avinatan Hasidim, Eyal Lubetzky +2
A sender holds a word x consisting of n blocks x_i, each of t bits, and wishes to broadcast a codeword to m receivers, R_1,...,R_m. Each receiver R_i is interested in one block, an…
k-Wise Independent Random Graphs
Noga Alon, Asaf Nussboim
We study the k-wise independent relaxation of the usual model G(N,p) of random graphs where, as in this model, N labeled vertices are fixed and each edge is drawn with probability…
Spanning directed trees with many leaves
N Alon, F. V. Fomin, G. Gutin +2
The {\sc Directed Maximum Leaf Out-Branching} problem is to find an out-branching (i.e. a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In th…
The maximum number of perfect matchings in graphs with a given degree sequence
Noga Alon, Shmuel Friedland
We show that the number of perfect matching in a simple graph with an even number of vertices and degree sequence is at most $\prod_{i=1}^n (d_i !)^{\frac{1…