连通简单$r$-一致超图的约化

Reductions of Connected Simple $r$-Uniform Hypergraphs

中文关键词:  图类  约化  一致超图

英文关键词:graph families  reductions  uniform hypergraphs

中文摘要:

      本文证明了如果$G$是阶数大于2的连通简单$r$-一致超图,那么$G$中存在一条边$e$使得$G-e-V_1(e)$是连通简单$r$-一致超图.这个约化叫做合成格拉木约化.我们刻画了单边消去或单边收缩下的极小连通简单$r$-一致超图.

英文摘要:

      It is proved in this paper that if $G$ is a simple connected $r$-uniform hypergraph with $\|G\|\geq 2$, then $G$ has an edge $e$ such that $G - e - V_1(e)$ is also a simple connected $r$-uniform hypergraph. This reduction is naturally called a combined Graham reduction. Under the simple reductions of single edge removals and single edge contractions, the minor minimal connected simple $r$-uniform hypergraphs are also determined.