Equicovering Subgraphs of Graphs and Hypergraphs

Abstract

As a variation on the t-Equal Union Property (t-EUP) introduced by Lindstrom, we introduce the t-Equal Valence Property (t-EVP) for hypergraphs: a hypergraph satisfies the t-EVP if there are t pairwise edge-disjoint subhypergraphs such that for each vertex v, the degree of v in all t subhypergraphs is the same. In the t-EUP, the subhypergraphs just have the same sets of vertices with positive degree. For both the 2-EUP and the 2-EVP, we characterize the graphs satisfying the property and determine the maximum number of edges in a graph not satisfying it. We also study the maximum number of edges in both k-uniform and general hypergraphs not satisfying the t-EVP.