Article ID Journal Published Year Pages File Type
5776907 Discrete Mathematics 2017 7 Pages PDF
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).
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,