✦ LIBER ✦

Induced matching extendable graphs

✍ Scribed by Jinjiang, Yuan

Publisher: John Wiley and Sons
Year: 1998
Tongue: English
Weight: 261 KB
Volume: 28
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199808)28:4<203::aid-jgt2>3.0.co;2-n

No coin nor oath required. For personal study only.

✦ Synopsis

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 ∼ = T × K 2 , where T is a tree.

(3) The only 3-regular connected IM-extendable graphs are C n × K 2 , for n ≥ 3, and C 2n (1, n), for n ≥ 2, where C 2n (1, n) is the graph with 2n vertices x 0 , x 1 , . . . , x 2n-1 , such that x i x j is an edge of C 2n (1, n) if either |i -j| ≡ 1 (mod 2n) or |i -j| ≡ n (mod 2n).

📜 SIMILAR VOLUMES

Extending matchings in claw-free graphs

✍ Michael D. Plummer 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 506 KB

Let G be a graph with a perfect matching and let n be an integer, has a perfect matching for every pair of points u and v in V(G). It is proved that every 3-connected claw-free graph is bicritical and for n>2, every (2n+ l)-connected claw-free graph is n-extendable. Matching extension in planar an

Extending matchings in planar graphs IV

✍ Michael D. Plummer 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 973 KB

Plummer, M.D., Extending matchings in planar graphs IV, Discrete Mathematics 109 (1992) 207-219. The structure of certain non-Zextendable planar graphs is studied first. In particular, 4-connected S-regular planar graphs which are not 2-extendable are investigated and examples of these are presented

Extending matchings in planar graphs V

✍ Michael D. Plummer 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 473 KB

A graph G on at least 2n + 2 vertices in n-extendable if every set of n independent edges extends to (i.e., is a subset of) a perfect matching in G. It is known that no planar graph is 3-extendable. In the present paper we continue to study 2-extendability in the plane. Suppose independent edges el

Induced matchings in bipartite graphs

✍ R.J. Faudree; A. Gyárfas; R.H. Schelp; Zs. Tuza 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 454 KB

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

A note on n-extendable graphs

✍ Qinglin Yu 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 249 KB

## Abstract A graph __G__ having a perfect matching is called n‐__extendable__ if every matching of size __n__ of __G__ can be extended to a perfect matching. In this note, we show that if __G__ is an __n__‐extendable nonbipartite graph, then __G__ + __e__ is (__n__ ‐ 1)‐extendable for any edge e ϵ