Hyperconnectivity of graphs (Q1086586): Difference between revisions

This paper introduces the concept of ''hyperconnectivity'' for graphs (and hypergraphs) and applies it to study some extremal problems in graph theory and some structure properties of graphs. For a fixed \(k>0\), \(n\geq k-1\) and a fixed set X of n vertices, matroid \(H^ n_ k\) is defined on the set of edges of K(X), the complete graph on X. A graph G on the vertex set X is k-hyperconnected if the set of its edges span \(H^ n_ k\); similarly C is k-acyclic if the set of its edges is independent in \(H^ n_ k\). \(H^ n_ 1\) is just the graphic matroid and thus a 1-hyperconnected graph is a connected graph and 1- acyclic graph is a forest. The definition of k-hyperconnectivity and of the matroid \(H^ n_ k\) is given (by an explicit representation of \(H^ n_ k\) over \({\mathbb{R}})\). These concepts are defined in the language of exterior algebra. Various properties of \(H^ n_ k\) are proved.