Journal of Combinatorics

Volume 5 (2014)

Number 3

Augmenting and preserving partition connectivity of a hypergraph

Pages: 271 – 289

DOI: https://dx.doi.org/10.4310/JOC.2014.v5.n3.a1

Authors

Xiaofeng Gu (Department of Mathematics and Computer Science, University of Wisconsin, Superior, Wisc., U.S.A.)

Hong-Jian Lai (Department of Mathematics, West Virginia University, Morgantown, W.V., U.S.A.)

Abstract

Let $k$ be a positive integer. A hypergraph $H$ is $k$-partition-connected if for every partition $P$ of $V(H)$, there are at least $k(|P|-1)$ hyperedges intersecting at least two classes of $P$. In this paper, we determine the minimum number of hyperedges in a hypergraph whose addition makes the resulting hypergraph $k$-partition-connected. We also characterize the hyperedges of a $k$-partition-connected hypergraph whose removal will preserve $k$-partition-connectedness.

Published 29 October 2014