Equicovering Subgraphs of Graphs and Hypergraphs

Abstract

As a variation on the $t$-Equal Union Property ($t$-EUP) introduced by Lindström, 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.