✦ LIBER ✦

Collapsible graphs and matchings

✍ Scribed by Zhi-Hong Chen; Hong-Jian Lai

Publisher: John Wiley and Sons
Year: 1993
Tongue: English
Weight: 286 KB
Volume: 17
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190170506

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A graph G is collapsible if for every even subset R ⊆ V(G), there is a spanning connected subgraph of G whose set of odd degree vertices is R. A graph is reduced if it does not have nontrivial collapsible subgraphs. Collapsible and reduced graphs are defined and studied in [4]. In this article, we obtain a lower bound on the size of a maximum matching in a reduced graph. As an application, we verify and strengthen the Benhocine, Clark, Köhler, and Veldman conjecture [1], when restricted to 3‐edge‐connected graphs, by showing that for n large, a simple graph G with order n and with k′(G) ≥ 3 is collapsible or is contractible to the Petersen graph if for each edge uv ∈ E(G), d(u) + d(v) ≥ (n/5) − 2. We also characterize the extremal graphs. © 1993 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

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

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.

Disjoint matchings of graphs

✍ Kenneth Lebensold 📂 Article 📅 1977 🏛 Elsevier Science 🌐 English ⚖ 250 KB

Matchings in polytopal graphs

✍ B. Grünbaum 📂 Article 📅 1974 🏛 John Wiley and Sons 🌐 English ⚖ 667 KB

Graphs with independent perfect matching

Graphs with independent perfect matchings

✍ Marcelo H. de Carvalho; Cláudio L. Lucchesi; U. S. R. Murty 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 241 KB

A graph with at least two vertices is matching covered if it is connected and each edge lies in some perfect matching. A matching covered graph G is extremal if the number of perfect matchings of G is equal to the dimension of the lattice spanned by the set of incidence

Induced matchings in bipartite graphs

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