𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Matchings in hypergraphs of large minimum degree

✍ Scribed by Daniela Kühn; Deryk Osthus

Publisher
John Wiley and Sons
Year
2006
Tongue
English
Weight
112 KB
Volume
51
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

It is well known that every bipartite graph with vertex classes of size n whose minimum degree is at least n/2 contains a perfect matching. We prove an analog of this result for hypergraphs. We also prove several related results that guarantee the existence of almost perfect matchings in r‐uniform hypergraphs of large minimum degree. Our bounds on the minimum degree are essentially best possible. © 2005 Wiley Periodicals, Inc. J Graph Theory 51: 269–280, 2006

📜 SIMILAR VOLUMES

Cycle lengths in graphs with large minim
Cycle lengths in graphs with large minimum degree
✍ V. Nikiforov; R. H. Schelp 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 114 KB 👁 1 views

## Abstract Our main result is the following theorem. Let __k__ ≥ 2 be an integer, __G__ be a graph of sufficiently large order __n__, and __δ__(__G__) ≥ __n__/__k__. Then: __G__ contains a cycle of length __t__ for every even integer __t__ ∈ [4, __δ__(__G__) + 1]. If __G__ is nonbipartite then

Maximal matchings in graphs with large n
Maximal matchings in graphs with large neighborhoods of independent vertices
✍ I. Rinsma; C. H. C. Little; D. R. Woodall 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 174 KB

## Abstract We obtain lower bounds on the size of a maximum matching in a graph satisfying the condition |__N(X)__| ≥ __s__ for every independent set __X__ of __m__ vertices, thus generalizing results of Faudree, Gould, Jacobson, and Schelp for the case __m__ = 2.

Light subgraphs in planar graphs of mini
Light subgraphs in planar graphs of minimum degree 4 and edge-degree 9
✍ B. Mohar; R. Škrekovski; H.-J. Voss 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 326 KB 👁 1 views

## Abstract A graph __H__ is light in a given class of graphs if there is a constant __w__ such that every graph of the class which has a subgraph isomorphic to __H__ also has a subgraph isomorphic to __H__ whose sum of degrees in __G__ is ≤ __w__. Let $\cal G$ be the class of simple planar graphs

Balloons, cut-edges, matchings, and tota
Balloons, cut-edges, matchings, and total domination in regular graphs of odd degree
✍ Suil O; Douglas B. West 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 148 KB 👁 1 views

## Abstract A __balloon__ in a graph __G__ is a maximal 2‐edge‐connected subgraph incident to exactly one cut‐edge of __G__. Let __b__(__G__) be the number of balloons, let __c__(__G__) be the number of cut‐edges, and let α′(__G__) be the maximum size of a matching. Let \documentclass{article}\usep

On Light Edges and Triangles in Planar G
On Light Edges and Triangles in Planar Graphs of Minimum Degree Five
✍ Oleg V. Borodin; Daniel P. Sanders 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 342 KB 👁 1 views

## Abstract This paper presents two tight inequalities for planar graphs of minimum degree five. An edge or face of a plane graph is light if the sum of the degrees of the vertices incident with it is small. A light edge inequality is presented which shows that planar graphs of minimum degree five