𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On disjoint matchings in cubic graphs

✍ Scribed by Vahan V. Mkrtchyan; Samvel S. Petrosyan; Gagik N. Vardanyan

Book ID
108114216
Publisher
Elsevier Science
Year
2010
Tongue
English
Weight
562 KB
Volume
310
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Disjoint matchings of graphs
Disjoint matchings of graphs
✍ Kenneth Lebensold πŸ“‚ Article πŸ“… 1977 πŸ› Elsevier Science 🌐 English βš– 250 KB
Induced matchings in cubic graphs
Induced matchings in cubic graphs
✍ Peter HorΓ‘k; He Qing; William T. Trotter πŸ“‚ Article πŸ“… 1993 πŸ› John Wiley and Sons 🌐 English βš– 527 KB

## Abstract In this paper, we show that the edge set of a cubic graph can always be partitioned into 10 subsets, each of which induces a matching in the graph. This result is a special case of a general conjecture made by ErdΓΆs and NeΕ‘etΕ™il: For each __d__ β‰₯ 3, the edge set of a graph of maximum de

Small maximal matchings of random cubic
Small maximal matchings of random cubic graphs
✍ H. Assiyatun; W. Duckworth πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 330 KB

## Abstract We consider the expected size of a smallest maximal matching of cubic graphs. Firstly, we present a randomized greedy algorithm for finding a small maximal matching of cubic graphs. We analyze the average‐case performance of this heuristic on random __n__‐vertex cubic graphs using diffe