𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the connectivity of graphs generated by a sum of random mappings

✍ Scribed by Jerzy Jaworski; Michał Karoński

Publisher
John Wiley and Sons
Year
1993
Tongue
English
Weight
537 KB
Volume
17
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We consider four models of random directed multigraphs with n labeled vertices of out‐degree d. First we establish formal relationships between our models with respect to exact and asymptotic (as n → ∞) probabilities of possessing a graph monotone property. We also study the asymptotic behavior of the strength of connectivity of the underlying simple graphs when d = o(n). © 1993 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

Connectivity of random regular graphs ge
Connectivity of random regular graphs generated by the pegging algorithm
✍ Pu Gao 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 149 KB 👁 1 views

## 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

On k-leaf connectivity of a random graph
On k-leaf connectivity of a random graph
✍ Thomasz Luczak 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 367 KB

We prove that, in a random graph with n vertices and N = cn log n edges, the subgraph generated by a set of all vertices of degree at least k + 1 is k-leaf connected for c > f . A threshold function for k-leaf connectivity is also found. ## 1. MAIN RESULTS Let G = (V(G),E(G)) be a graph, where V (

A Short Proof of a Theorem Concerning De
A Short Proof of a Theorem Concerning Degree Sums and Connectivity on Hamiltonian Graphs
✍ Bing Wei 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 74 KB

proved that if G is a 2-connected graph with n vertices such that d(u)+d(v)+d(w) n+} holds for any triple of independent vertices u, v, and w, then G is hamiltonian, where } is the vertex connectivity of G. In this note, we will give a short proof of the above result.