𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Random packing by ρ-connected ρ-regular graphs

✍ Scribed by Lowell W. Beineke; Peter Hamburger; William D. Weakley

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
338 KB
Volume
160
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

A graph G is packable by the graph F if its edges can be partitioned into copies of F. If deleting the edges of any F-packable subgraph from G leaves an F-packable graph, then G is

The minimal F-forbidden graphs provide a characterization of randomly F-packable graphs. We show that for each p-connected p-regular graph F with p > 1, there is a set ~(F) of minimal F-forbidden graphs of a simple form, such that any other minimal F-forbidden graph can be obtained from a graph in ,~(F) by a process of identifying vertices and removing copies of F.

When F is a connected strongly edge-transitive graph having more than one edge (such as a cycle or hypercube), there is only one graph in ~(F).

📜 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 the connectivity of graphs generated
On the connectivity of graphs generated by a sum of random mappings
✍ Jerzy Jaworski; Michał Karoński 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 537 KB

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