𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Matching Covered Graphs and Subdivisions ofK4and[formula]

✍ Scribed by Marcelo H. de Carvalho; Cláudio L. Lucchesi

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
226 KB
Volume
66
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

We give a very simple proof that every non-bipartite matching covered graph contains a nice subgraph that is an odd subdivision of K 4 or C 6 . It follows immediately that every brick different from K 4 and C 6 has an edge whose removal preserves the matching covered property. These are classical and very useful results due to Lova sz.

📜 SIMILAR VOLUMES

Subdivisions, parity and well-covered gr
Subdivisions, parity and well-covered graphs
✍ Caro, Yair 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 121 KB 👁 2 views

A graph is well-covered if every maximal independent set is maximum. This concept, introduced by Plummer in 1970 (J. Combin. Theory 8 (1970)), is the focal point of much interest and current research. We consider well-covered 2-degenerate graphs and supply a structural (and polynomial time algorithm

Optimal Ear Decompositions of Matching C
Optimal Ear Decompositions of Matching Covered Graphs and Bases for the Matching Lattice
✍ Marcelo H. de Carvalho; Cláudio L. Lucchesi; U.S.R. Murty 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 225 KB

A Petersen brick is a graph whose underlying simple graph is isomorphic to the Petersen graph. For a matching covered graph G, b(G) denotes the number of bricks of G, and p(G) denotes the number of Petersen bricks of G. An ear decomposition of G is optimal if, among all ear decompositions of G, it u

Total matchings and total coverings of g
Total matchings and total coverings of graphs
✍ Y. Alavi; M. Behzad; L. M. Lesniak-Foster; E. A. Nordhaus 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 280 KB

## Abstract In graph theory, the related problems of deciding when a set of vertices or a set of edges constitutes a maximum matching or a minimum covering have been extensively studied. In this paper we generalize these ideas by defining total matchings and total coverings, and show that these set