  Connectivity is a central notion of graph theory and plays an important role
in graph algorithm design and applications. With emerging new applications in
networks, a new type of graph connectivity problem has been getting more
attention--hedge connectivity. In this paper, we consider the model of hedge
graphs without hedge overlaps, where edges are partitioned into subsets called
hedges that fail together. The hedge connectivity of a graph is the minimum
number of hedges whose removal disconnects the graph. This model is more
general than the hypergraph, which brings new computational challenges. It has
been a long open problem whether this problem is solvable in polynomial time.
In this paper, we study the combinatorial properties of hedge graph
connectivity without hedge overlaps, based on its extremal conditions as well
as hedge contraction operations, which provide new insights into its
algorithmic progress.
