✦ LIBER ✦

Connectivity of random regular graphs generated by the pegging algorithm

✍ Scribed by Pu Gao

Publisher: John Wiley and Sons
Year: 2010
Tongue: English
Weight: 149 KB
Volume: 65
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20472

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We study the connectivity of random d‐regular graphs which are recursively generated by an algorithm motivated by a peer‐to‐peer network. We show that these graphs are asymptotically almost surely d‐connected for any even constant d⩾4. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 185–197, 2010

📜 SIMILAR VOLUMES

The generalized acyclic edge chromatic n

The generalized acyclic edge chromatic number of random regular graphs

✍ Stefanie Gerke; Catherine Greenhill; Nicholas Wormald 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 224 KB 👁 1 views

## Abstract The __r__‐acyclic edge chromatic number of a graph is defined to be the minimum number of colors required to produce an edge coloring of the graph such that adjacent edges receive different colors and every cycle __C__ has at least min(|__C__|, __r__) colors. We show that (__r__ − 2)__d