𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Graphs with the balas—uhry property

✍ Scribed by M. Kano; S. Poljak

Book ID
102338091
Publisher
John Wiley and Sons
Year
1990
Tongue
English
Weight
287 KB
Volume
14
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We characterize graphs H with the following property: Let G be a graph and F be a subgraph of G such that (i) each component of F is isomorphic to H or K~2~, (ii) the order of F is maximum, and (iii) the number of H‐components in F is minimum subject to (ii). Then a maximum matching of F is also a maximum matching of G. This result is motivated by an analogous property of fractional matchings discovered independently by J. P. Uhry and E. Balas.

📜 SIMILAR VOLUMES

Nonbipartite graphs with the repeated de
Nonbipartite graphs with the repeated degree property
✍ S?olt�s, L?ubomi?r 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 100 KB

A graph G has the repeated degree property if there is an integer n such that for each graph H with at least n vertices, either H or its complement contains a copy of G in which two vertices have the same degree in H. The minimum such number n is the repeated degree number of G. We extend work of Ch

Factors in graphs with odd-cycle propert
Factors in graphs with odd-cycle property
✍ Ciping Chen; Jianfang Wang 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 634 KB

Chen, C. and J. Wang, Factors in graphs with odd-cycle property, Discrete Mathematics 112 (1993) 29-40. We present some conditions for the existence of a (g,f)-factor or a (g,f)-parity factor in a graph G with the odd-cycle property that any two odd cycles of G either have a vertex in common or are