Back to Search
Start Over
An approximate ore-type result for tight Hamilton cycles in uniform hypergraphs.
- Source :
-
Discrete Mathematics . Jul2017, Vol. 340 Issue 7, p1528-1534. 7p. - Publication Year :
- 2017
-
Abstract
- A Hamilton ℓ -cycle in a k -uniform hypergraph of n -vertex is an ordering of all vertices, combined with an ordered subset C of edges, such that any two consecutive edges share exactly ℓ vertices and each edge in C contains k consecutive vertices. A classic result of O. Ore in 1960 is that if the degree sum of any two independent vertices in an n -vertex graph is at least n , then the graph contains a Hamiltonian cycle. Naturally, we consider to generalize it to hypergraphs situation. In this paper, we prove the following theorems. (i) For any n ≥ 4 k 2 , there is an n -vertex k -uniform hypergraph, with degree sum of any two strongly independent sets of k − 1 vertices bigger than 2 n − 4 ( k − 1 ) , contains no Hamilton l -cycle, 1 ≤ ℓ ≤ k − 1 . (ii) If the degree sum of two weakly independent sets of k − 1 vertices in an n -vertex k -uniform hypergraph is ( 1 + o ( 1 ) ) n , then the hypergraph contains a Hamilton ( k − 1 ) -cycle, where two distinct sets of k − 1 vertices are weakly (strongly) independent if there exist no edge containing the union of them (intersecting both of them). [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 340
- Issue :
- 7
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 122454748
- Full Text :
- https://doi.org/10.1016/j.disc.2017.02.018