Invertible families of sets of bounded degree

Details Invertible families of sets of bounded degree Invertible families of sets of bounded degree

1994-09-16

arxiv.org/abs/math/9409214v1

Mathematics

Combinatorics

9 pages

Scientific paper

Let H = (H,V) be a hypergraph with edge set H and vertex set V. Then hypergraph H is invertible iff there exists a permutation pi of V such that for all E belongs to H(edges) intersection of(pi(E) and E)=0. H is invertibility critical if H is not invertible but every hypergraph obtained by removing an edge from H is invertible. The degree of H is d if |{E belongs to H(edges)|x belongs to E}| =< d for each x belongs to V Let i(d) be the maximum number of edges of an invertibility critical hypergraph of degree d. Theorem: i(d) =< (d-1) {2d-1 choose d} + 1. The proof of this result leads to the following covering problem on graphs: Let G be a graph. A family H is subset of (2^{V(G)} is an edge cover of G iff for every edge e of G, there is an E belongs to H(edge set) which includes e. H(edge set) is a minimal edge cover of G iff for H' subset of H, H' is not an edge cover of G. Let b(d) (c(d)) be the maximum cardinality of a minimal edge cover H(edge set) of a complete bipartite graph (complete graph) where H(edge set) has degree d. Theorem: c(d)=< i(d)=

Affiliated with

Also associated with

No associations

Rating

Invertible families of sets of bounded degree does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Invertible families of sets of bounded degree, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Invertible families of sets of bounded degree will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-566372