2
$\begingroup$

Consider a connected graph G which has n vertices and m edges. If m = n − 1, then we know immediately that G is a tree; which is notable because it has no cycles — between any two vertices, there is exactly one path. If m = n, we know that G contains exactly one cycle. And if m > n, we know that G has multiple cycles. (Note that m < n − 1 is impossible for connected graphs.)

Now consider a connected hypergraph H, where each edge contains exactly k vertices (it is k-uniform), where k ≥ 2. Is there any similar sort of structural property of H, or graph class to which H belongs, if it has exactly n edges? At most n − 1 edges?

More precisely: suppose that there is a mapping from the edges to the vertices, such that each edge is mapped to a distinct vertex to which it is incident. (If you look at the factor graph F of the hypergraph — a bipartite graph between a collection of "hyperedge-nodes" and "vertex nodes", where a hyperedge-node e is adjacent to a vertex-node v in F, if and only if e is an edge in H incident to v — then this is equivalent to there being a matching which covers the hyperedge-nodes.) Given that H which has such a mapping, suppose that the mapping is in fact bijective. Does this entail any important properties of H? What if this function is injective, but not surjective?

  • 0
    For (V,E) a clutter consider the set of set partitions p of E whose set of unions Union^*(p) is a clutter that is tree. This poset has a unique maximum set partition s (but I haven't found an easy proof of this fact). The blocks of s are clutters that I call _blobs_. In other words, every clutter is a tree of blobs. Blobs are not characterized by density value or 2-connectedness, and I haven't found a way to enumerate them directly. But they can be defined as clutters with no contraction that is a tree.2011-10-08

0 Answers 0