✦ LIBER ✦

Matchings and matching extensions in graphs

✍ Scribed by Ciping Chen

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 360 KB
Volume: 186
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(97)00182-9

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a graph with a perfect matching and k be an integer such that l~<k< I V(G)l/2.

Then G is said to be k-extendable if every matching of size k in G extends to a perfect matching of G. Plummer (1994) proved that every (2k + 1)-connected K~,s-free graph of even order is k-extendable. In this paper, it was proved that every (2k + n -2)-connected Kl,,,-free graph of even order is k-extendable. Also, an answer to the problem of characterizing maximal k-extendable graphs posted by and Saito (1989/90) is given. Besides, we show that a regular graph of even order belongs to the first class if its any two odd cycles have at least a vertex in common.

📜 SIMILAR VOLUMES

Toughness and matching extension in grap

Toughness and matching extension in graphs

✍ M.D. Plummer 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 588 KB

Matching extension in the powers ofn-con

Matching extension in the powers ofn-connected graphs

✍ Walcher, Kara Lee 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 288 KB 👁 1 views

Let G be a graph on p vertices. Then for a positive integer n, G is said to be n-extendible if (i) TI < p / 2 , iii) G has a set of n independent edges, and (iii) every such set is contained in a perfect matching of G. In this paper we will show that if p is even and G is TIconnected, then Gk is ([$

Matching extension and the genus of a gr

Matching extension and the genus of a graph

✍ Michael D Plummer 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 455 KB

Matching graphs

✍ Eroh, Linda; Schultz, Michelle 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 336 KB

The matching graph M (G) of a graph G is that graph whose vertices are the maximum matchings in G and where two vertices M 1 and M 2 of M (G) this graph models a metric space whose metric is defined on the set of maximum matchings in G. Which graphs are matching graphs of some graph is not known in

Matching and multidimensional matching i

Matching and multidimensional matching in chordal and strongly chordal graphs

✍ Elias Dahlhaus; Marek Karpinski 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 877 KB

Chordal graphs are graphs with the property that each cycle of length greater than 3 has two non-consecutive vertices that are joined by an edge. An important subclass of chordal graphs are strongly chordal graphs (Farber, 1983). Chordal graphs appear for example in the design of acyclic data base s

Matchings and walks in graphs

✍ C. D. Godsil 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 527 KB

## Abstract The matching polynomial α(__G, x__) of a graph __G__ is a form of the generating function for the number of sets of __k__ independent edges of __G__. in this paper we show that if __G__ is a graph with vertex __v__ then there is a tree __T__ with vertex __w__ such that \documentclass{ar