Aspects of random graphs: colourings, walkers and hamiltonian cycles.

• Autores: Xavier Perez Gimenez
• Directores de la Tesis: Josep Díaz Cort (dir. tes.)
• Lectura: En la Universitat Politècnica de Catalunya (UPC) ( España ) en 2007
• Idioma: español
• Tribunal Calificador de la Tesis: Marc Noy Serrano (presid.) , María José Serna Iglesias (secret.) , Colin McDiarmid (voc.) , Nick Wormald (voc.) , Lefteris Kirousis (voc.)
• Texto completo no disponible (Saber más ...)
• Resumen

  • This dissertation presents the author's work in some problems involving different models of random graphs, First it contains a technical contribution towards solving the open problem of deciding whether with high probability a random $5$-regular graph can be coloured with three colours. Next, the author proposes a model for the establishment and maintenance of communication between agents in a \emph{mobile ad-hoc network} ({\sc manet}), which is called the {\em walkers model}. We assume that the agents move through a fixed environment modelled by a motion graph, and are able to communicate only if they are at a distance of at most $d$. As the agents move randomly, we analyse how the connectivity between a set of $w$ agents evolves over time, asymptotically for a large number $N$ of vertices, when $w$ also grows large. The particular topologies of the environment which are studied here are the cycle and the toroidal grid. For the latter, the results apply under any $\ell_p$-normed distance, for $1\leq p\leq\infty$. Then, the dissertation follows with a continuous counterpart of the walkers model. Namely, it presents a model for {\sc manet}s based on random geometric graphs over the $2$-dimensional unit torus, where each node moves under the {\em random walk} mobility model. More precisely, our model starts from a random geometric graph over the torus \UT, with $n$ nodes and radius exactly at the connectivity threshold $r_c$. Then each node chooses independently a random angle in $[0,2\pi)$ and moves for a number $m$ of steps a fixed distance $s>0$ in that direction. After these steps, each node again chooses a new angle and starts moving in that new direction, repeating the change of direction every $m$ steps. We compute the expected number of steps for which the resulting graph stays connected or disconnected. In addition, for static random geometric graphs with radius at the connectivity threshold $r_c$, we provide asymptotic expressions on the probability of