Reductions of Connected Simple $r$-Uniform Hypergraphs
Received:September 11, 2013  Revised:October 10, 2014
Key Words: graph families   reductions   uniform hypergraphs  
Fund Project:Supported by NRF South Africa and the National Natural Science Foundation of China (Grant No.11161032).
Author NameAffiliation
Sheng BAU School of Mathematics, University of the Witwatersrand, Johannesbury, South Africa
Institute of Discrete Mathematics, Inner Mongolia University of Nationalities, Inner Mongolia 028005, P. R. China 
Jirimutu Institute of Discrete Mathematics, Inner Mongolia University of Nationalities, Inner Mongolia 028005, P. R. China 
Changchang YIN Center for Discrete Mathematics, Fuzhou University, Fujian 350002, P. R. China 
Hits: 2889
Download times: 2769
Abstract:
      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.
Citation:
DOI:10.3770/j.issn:2095-2651.2015.01.002
View Full Text  View/Add Comment