Packing arborescences in random digraphs

Carlos Hoppen, Roberto F. Parente and Cristiane M. Sato

We study the problem of packing arborescences in the random digraph D(n,p), where each possible arc is included uniformly at random with probability p=p(n). Let λ (D(n,p)) denote the largest integer λ≥0 such that, for all 0≤ℓ≤λ, we have ∑i=0ℓ−1(ℓ−i)|{v:din(v)=i}|≤ℓ. We show that the maximum number of arc-disjoint arborescences in D(n,p) is λ(D(n,p)) a.a.s. We also give tight estimates for λ(D(n,p)) depending on the range of p.

The whole paper is available here.

 

NeuroMat

O Centro de Pesquisa, Inovação e Difusão em Neuromatemática está sediado na Universidade de São Paulo e é financiado pela FAPESP (Fundação de Amparo à Pesquisa do Estado de São Paulo).

 

Login do usuário

 

Contato

Endereço:
Rua do Matão, 1010 - Cidade Universitária - São Paulo - SP - Brasil. 05508-090. Veja o mapa.

Telefone:
55 11 3091-1717

Email:
neuromat@numec.prp.usp.br

Contatos de mídia:
comunicacao@numec.prp.usp.br