𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Disjoint Hamilton cycles in the random geometric graph

✍ Scribed by Tobias Müller,; Xavier Pérez-Giménez;; Nicholas Wormald

Publisher
John Wiley and Sons
Year
2011
Tongue
English
Weight
270 KB
Volume
68
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the standard random geometric graph process in which n vertices are placed at random on the unit square and edges are sequentially added in increasing order of edge-length. For fixed k ≥ 1, we prove that the first edge in the process that creates a k-connected graph coincides a.a.s. with the first edge that causes the graph to contain k / 2 pairwise edge-disjoint Hamilton cycles (for even k), or (k -1) / 2 Hamilton cycles plus one perfect matching, all of them pairwise edge-disjoint (for

📜 SIMILAR VOLUMES

Edge disjoint Hamilton cycles in sparse
Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at leastk
✍ Bollob�s, B.; Cooper, C.; Fenner, T. I.; Frieze, A. M. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 175 KB 👁 3 views

Let G n,m,k denote the space of simple graphs with n vertices, m edges, and minimum degree at least k, each graph G being equiprobable. Let G have property A k , if G contains (k -1)/2 edge disjoint Hamilton cycles, and, if k is even, a further edge disjoint matching of size n/2 . We prove that, for

Generating and Counting Hamilton Cycles
Generating and Counting Hamilton Cycles in Random Regular Graphs
✍ Alan Frieze; Mark Jerrum; Michael Molloy; Robert Robinson; Nicholas Wormald 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 216 KB

Let G be chosen uniformly at random from the set G G r, n of r-regular graphs w x Ž . with vertex set n . We describe polynomial time algorithms that whp i find a Ž . Hamilton cycle in G, and ii approximately count the number of Hamilton cycles in G.