✦ LIBER ✦

Matchings and transversals in hypergraphs, domination and independence-in trees

✍ Scribed by E.J Cockayne; S.T Hedetniemi; P.J Slater

Publisher: Elsevier Science
Year: 1979
Tongue: English
Weight: 199 KB
Volume: 26
Category: Article
ISSN: 0095-8956
DOI: 10.1016/0095-8956(79)90044-3

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Partial Steiner systems and matchings in

Partial Steiner systems and matchings in hypergraphs

✍ A.V. Kostochka; V. Rödl 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 203 KB

For tk, a t, k T-system is a k-uniform hypergraph H such that any two Ž . distinct edges of H have at most t y 1 vertices in common. Clearly, any t, k -system on n n k

Perfect fractional matchings in random h

Perfect fractional matchings in random hypergraphs

✍ Michael Krivelevich 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 890 KB

Given an r-uniform hypergraph H = (V, E ) on ( V ( = n vertices, a real-valued function f(e) 5 1 for all u E V and C e E E f(e) = n/r. Considering a random r-uniform hypergraph process of n vertices, we show that with probability tending to 1 as n + m , at the very moment to when the last isolated

Transversal hypergraphs to perfect match

Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms

✍ Endre Boros; Khaled Elbassioni; Vladimir Gurvich 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 285 KB

A minimal blocker in a bipartite graph G is a minimal set of edges the removal of which leaves no perfect matching in G. We give an explicit characterization of the minimal blockers of a bipartite graph G. This result allows us to obtain a polynomial delay algorithm for finding all minimal blockers

Matchings in hypergraphs of large minimu

Matchings in hypergraphs of large minimum degree

✍ Daniela Kühn; Deryk Osthus 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 112 KB

## 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 mat

Independence and hamiltonicity in 3-domi

Independence and hamiltonicity in 3-domination-critical graphs

✍ Favaron, Odile; Tian, Feng; Zhang, Lei 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB 👁 3 views

Let δ, γ, i and α be respectively the minimum degree, the domination number, the independent domination number and the independence number of a graph G. The graph G is 3-γ-critical if γ = 3 and the addition of any edge decreases γ by 1. It was conjectured that any connected 3-γ-critical graph satisf

Transversals of subtree hypergraphs and

Transversals of subtree hypergraphs and the source location problem in digraphs

✍ Jan van den Heuvel; Matthew Johnson 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 134 KB

## Abstract A hypergraph __H__ = (__V__,__E__) is a subtree hypergraph if there is a tree __T__ on __V__ such that each hyperedge of __E__ induces a subtree of __T__. Since the number of edges of a subtree hypergraph can be exponential in __n__ = |__V__|, one can not always expect to be able to fin