Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5776907 | Discrete Mathematics | 2017 | 7 Pages |
Abstract
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â¥4k2, there is an n-vertex k-uniform hypergraph, with degree sum of any two strongly independent sets of kâ1 vertices bigger than 2nâ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).
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Yucong Tang, Guiying Yan,