Home » Keyword index

matching


Graph Theory » Infinite Graphs

Strong matchings and covers ★★★

Author(s): Aharoni

Let $ H $ be a hypergraph. A strongly maximal matching is a matching $ F \subseteq E(H) $ so that $ |F' \setminus F| \le |F \setminus F'| $ for every matching $ F' $. A strongly minimal cover is a (vertex) cover $ X \subseteq V(H) $ so that $ |X' \setminus X| \ge |X \setminus X'| $ for every cover $ X' $.

Conjecture   If $ H $ is a (possibly infinite) hypergraph in which all edges have size $ \le k $ for some integer $ k $, then $ H $ has a strongly maximal matching and a strongly minimal cover.

Keywords: cover; infinite graph; matching

Posted by mdevos
updated October 23rd, 2007
add new comment
Graph Theory » Basic G.T. » Matchings

Matchings extend to Hamiltonian cycles in hypercubes ★★

Author(s): Ruskey; Savage

Question   Does every matching of hypercube extend to a Hamiltonian cycle?

Keywords: Hamiltonian cycle; hypercube; matching

Posted by Jirka
updated September 28th, 2007
add new comment
Graph Theory » Hypergraphs

Ryser's conjecture ★★★

Author(s): Ryser

Conjecture   Let $ H $ be an $ r $-uniform $ r $-partite hypergraph. If $ \nu $ is the maximum number of pairwise disjoint edges in $ H $, and $ \tau $ is the size of the smallest set of vertices which meets every edge, then $ \tau \le (r-1) \nu $.

Keywords: hypergraph; matching; packing

Posted by mdevos
updated March 19th, 2007
add new comment
Syndicate content