13405734
On Random Symmetric Travelling Salesman Problems
Let the edges of the complete graphK nbe assigned independent uniform [0, 1] random edge weights. LetZTSP andZ2FAC be the weights of the minimum length travelling salesman tour and minimum weight 2-factor, respectively. We show thatwhp | ZTSP -Z2FAC| =o(1). The proof is obtained by the analysis of a polynomial time algorithm that finds a tour only a little longer thanZ2FAC.
12475992
On Markov Chains for Randomly H-Coloring a Graph
Let H=(W,F) be a graph without multiple edges, but with the possibility of having loops. Let G=(V,E) be a simple graph. A homomorphism c is a map c:V?W with the property that (v,w)?E implies that (c(v),c(w))?F. We will often refer to c(v) as the color of v and c as an H-coloring of G. We consider the problem of choosing a random H-coloring of G by Markov chain Monte Carlo. The probabilistic model we consider includes random proper colorings, random independent sets, and the Widom?Rowlinson and Beach models of statistical physics. We prove negative results for uniform sampling and a positive result for weighted sampling when H is a tree.
1964724
Optimal construction of edge-disjoint paths in random regular graphs
Given a graph G = (V, E) and a set of κ pairs of vertices in V, we are interested in finding, for each pair (ai, bi), a path connecting ai to bi such that the set of κ paths so found is edge-disjoint. (For arbitrary graphs the problem is NP-complete, although it is in P if κ is fixed.)We present a polynomial time randomized algorithm for finding edge-disjoint paths in the random regular graph Gn,r, for sufficiently large r. (The graph is chosen first, then an adversary chooses the pairs of end-points.) We show that almost every Gn,r is such that all sets of κ = Ω(n/log n) pairs of vertices can be joined. This is within a constant factor of the optimum.
6378032
Adding random edges to dense graphs
This paper investigates the addition of random edges to arbitrary dense graphs; in particular, we determine the number of random edges required to ensure various monotone properties including the appearance of a fixed size clique, small diameter and k-connectivity.
19308721
Maximum matchings in a class of random graphs
Let Vn = {1,2,…,n} and D(n, m) be the set of digraphs with vertex set Vn in which each v ϵ Vn has outdegree m. D(n, m) is chosen uniformly at random from D(n, m) and then D(n, m) is obtained by ignoring the orientation of the edges of D(n, m). We show that 
Limn → ∞n evenPr(D(n, 1) has a perfect matching) = 0 
, 
Limn → ∞n evenPr(D(n, 2) has a perfect matching) = 1 
.
6616465
Multi-Coloured Hamilton Cycles In Random Edge-Coloured Graphs
We define a space of random edge-coloured graphs Gn,m,κ which correspond naturally to edge κ-colourings of Gn,m. We show that there exist constants K0, K1 ≤ 21 such that, provided m ≥ K0n log n and κ ≥ K1n, then a random edge-coloured graph contains a multi-coloured Hamilton cycle with probability tending to 1 as the number of vertices n tends to infinity.
12252849
On the connectivity of randomm-orientable graphs and digraphs
We consider graphs and digraphs obtained by randomly generating a prescribed number of arcs incident at each vertex.We analyse their almost certain connectivity and apply these results to the expected value of random minimum length spanning trees and arborescences.We also examine the relationship between our results and certain results of Erdős and Rényi.