宝升,吉日木图,尹常长.连通简单$r$-一致超图的约化[J].数学研究及应用,2015,35(1):11~18
连通简单$r$-一致超图的约化
Reductions of Connected Simple $r$-Uniform Hypergraphs
投稿时间:2013-09-11  最后修改时间:2014-10-10
DOI:10.3770/j.issn:2095-2651.2015.01.002
中文关键词:  图类  约化  一致超图
英文关键词:graph families  reductions  uniform hypergraphs
基金项目:南非自然科学基金; 国家自然科学基金 (Grant No.11161032).
作者单位
宝升 约翰内斯堡金山大学, 南非 
吉日木图 内蒙古民族大学离散数学研究所, 内蒙古 通辽 028005 
尹常长 福州大学离散数学研究中心, 福建 福州 350002 
摘要点击次数: 1107
全文下载次数: 1515
中文摘要:
      本文证明了如果$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.
查看全文  查看/发表评论  下载PDF阅读器