Equicovering Subgraphs of Graphs and Hypergraphs

  • Ilkyoo Choi
  • Jaehoon Kim
  • Amelia Tebbe
  • Douglas B. West
Keywords: Graph, Hypergraph, Equal Union Property, Equal Valence Property

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.

Published
2014-03-17
Article Number
P1.62