1 February 2016 in European Journal of Combinatorics
19 September 2016 in Advances in Applied Probability
Given any two vertices u, v of a random geometric graph G(n, r), denote by dE(u, v) their Euclidean distance and by dE(u, v) their graph distance. The problem of finding upper bounds on dG(u, v) conditional on dE(u, v) that hold asymptotically almost surely has received quite a bit of attention in the literature. In this paper we improve the known upper bounds for values of r=ω(√logn) (that is, for r above the connectivity threshold). Our result also improves the best known estimates on the diameter of random geometric graphs. We also provide a lower bound on dE(u, v) conditional on dE(u, v).
1 January 2020 in SIAM Journal on Discrete Mathematics
A famous theorem of Dirac states that any graph on $n$ vertices with minimum degree at least $n/2$ has a Hamilton cycle. Such graphs are called Dirac graphs. Strengthening this result, we show the existence of rainbow Hamilton cycles in $\mu n$-bounded colorings of Dirac graphs for sufficiently small $\mu >0$.
7 February 2012 in The Electronic Journal of Combinatorics
An identifying code is a subset of vertices of a graph such that each vertex is uniquely determined by its neighbourhood within the identifying code. If $\gamma^{\text{ID}}(G)$ denotes the minimum size of an identifying code of a graph $G$, it was conjectured by F. Foucaud, R. Klasing, A. Kosowski and A. Raspaud that there exists a constant $c$ such that if a connected graph $G$ with $n$ vertices and maximum degree $d$ admits an identifying code, then $\gamma^{\text{ID}}(G)\leq n-\tfrac{n}{d}+c$. We use probabilistic tools to show that for any $d\geq 3$, $\gamma^{\text{ID}}(G)\leq n-\tfrac{n}{\Theta(d)}$ holds for a large class of graphs containing, among others, all regular graphs and all graphs of bounded clique number. This settles the conjecture (up to constants) for these classes of graphs. In the general case, we prove $\gamma^{\text{ID}}(G)\leq n-\tfrac{n}{\Theta(d^{3})}$. In a second part, we prove that in any graph $G$ of minimum degree $\delta$ and girth at least 5, $\gamma^{\text{ID}}(G)\leq(1+o_\delta(1))\tfrac{3\log\delta}{2\delta}n$. Using the former result, we give sharp estimates for the size of the minimum identifying code of random $d$-regular graphs, which is about $\tfrac{\log d}{d}n$.
26 January 2017 in Probability Theory and Related Fields
For a fixed degree sequence \({\mathcal {D}}=(d_1,\ldots ,d_n)\), let \(G({\mathcal {D}})\) be a uniformly chosen (simple) graph on \(\{1,\ldots ,n\}\) where the vertex i has degree \(d_i\). In this paper we determine whether \(G({\mathcal {D}})\) has a giant component with high probability, essentially imposing no conditions on \({\mathcal {D}}\). We simply insist that the sum of the degrees in \({\mathcal {D}}\) which are not 2 is at least \(\lambda (n)\) for some function \(\lambda \) going to infinity with n. This is a relatively minor technical condition, and when \({\mathcal {D}}\) does not satisfy it, both the probability that \(G({\mathcal {D}})\) has a giant component and the probability that \(G({\mathcal {D}})\) has no giant component are bounded away from 1.