Cleaning Random d-Regular Graphs with Brooms |
| |
Authors: | Pawe? Pra?at |
| |
Institution: | 1. Department of Mathematics, West Virginia University, Morgantown, WV, 26506-6310, USA
|
| |
Abstract: | A model for cleaning a graph with brushes was recently introduced. Let α = (v
1, v
2, . . . , v
n
) be a permutation of the vertices of G; for each vertex v
i
let ${N^+(v_i)=\{j: v_j v_i \in E {\rm and} j>\,i\}}${N^+(v_i)=\{j: v_j v_i \in E {\rm and} j>\,i\}} and N-(vi)={j: vj vi ? E and j < i}{N^-(v_i)=\{j: v_j v_i \in E {\rm and} j<\,i\}} ; finally let ba(G)=?i=1n max{|N+(vi)|-|N-(vi)|,0}{b_{\alpha}(G)=\sum_{i=1}^n {\rm max}\{|N^+(v_i)|-|N^-(v_i)|,0\}}. The Broom number is given by B(G) = max
α
b
α
(G). We consider the Broom number of d-regular graphs, focusing on the asymptotic number for random d-regular graphs. Various lower and upper bounds are proposed. To get an asymptotically almost sure lower bound we use a degree-greedy
algorithm to clean a random d-regular graph on n vertices (with dn even) and analyze it using the differential equations method (for fixed d). We further show that for any d-regular graph on n vertices there is a cleaning sequence such at least n(d + 1)/4 brushes are needed to clean a graph using this sequence. For an asymptotically almost sure upper bound, the pairing
model is used to show that at most n(d+2?{d ln2})/4{n(d+2\sqrt{d \ln 2})/4} brushes can be used when a random d-regular graph is cleaned. This implies that for fixed large d, the Broom number of a random d-regular graph on n vertices is asymptotically almost surely
\fracn4(d+Q(?d)){\frac{n}{4}(d+\Theta(\sqrt{d}))}. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|