𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Induced matchings in cubic graphs

✍ Scribed by Peter Horák; He Qing; William T. Trotter

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

No coin nor oath required. For personal study only.

✦ Synopsis

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 degree d can always be partitioned into [5__d__^2^/4] subsets each of which induces a matching. © 1993 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

Induced matchings in bipartite graphs
Induced matchings in bipartite graphs
✍ R.J. Faudree; A. Gyárfas; R.H. Schelp; Zs. Tuza 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 454 KB
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

Induced forests in cubic graphs
Induced forests in cubic graphs
✍ William Staton 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 151 KB

Bounds are obtained for the number of vertices in a largest induced forest in a cubic graph with large girth. In particular, as girth increases without bound, the ratio of the number of vertices in a largest induced forest to the number of vertices in the whole graph approaches 3/4. The point arbof

Counting Matchings in Graphs
Counting Matchings in Graphs
✍ E.J. Farrell 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 488 KB

A general formula is derivedfor the matching polynomial of an arbitrary graph G. This yields a methodfor counting matchings in graphs. From the general formula, explicit formulae are deducedfor the number of k-matchings in several well-known families of graphs.

Induced matching extendable graphs
Induced matching extendable graphs
✍ Jinjiang, Yuan 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 261 KB

We say that a simple graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. The main results of this paper are as follows: (1) For every connected IM-extendable graph 2 |V (G)| -2; the equality holds if and only if G ∼