Let G be a graph of order n. For graph to be Hamiltonian, beginning with Dirac's classic result in 1952, Dirac's theorem was followed by that of Ore in 1960. In 1984, Fan generalized Dirac's theorem and Or...Let G be a graph of order n. For graph to be Hamiltonian, beginning with Dirac's classic result in 1952, Dirac's theorem was followed by that of Ore in 1960. In 1984, Fan generalized Dirac's theorem and Ore's theorem as if G is a 2-connected graph of order n and max {d (u),d (v)}≥n/2 for each pair of vertices u and v with d (u,v)=2, then G is hamiltonian. In 1991, Faudree et al proved that if G is a 2-connected graph and, |N (u)∪N (v)|+δ(G)≥n for each pair of nonadjacent vertices u,v∈V(G), then G is hamiltonian. This paper generalizes the above conditions of Dirac, Ore, Fan and Faudree et al in the case of 3-connected graph and proves that if G is a 3-connected graph of order n and max{|N(x)∪ N (y)| +d (u), |N (w)∪N (z)|+d (v)}≥n for every choice of 6 Essential independent vertices, then G is hamiltonian.展开更多
In this note,we show a sharp lower bound of min{Σ_(i=1)^(k)dG(u_(i)):u1u2...uk is a path of(2-)connected G}on its order such that(k-1)-iterated line graphs L^(k-1)(G)are hamiltonian.
基金Research supported by NSF of Hainan (No.10501) NSF of the Education Departmant of Hainan(No.Hjkj 200529)
文摘Let G be a graph of order n. For graph to be Hamiltonian, beginning with Dirac's classic result in 1952, Dirac's theorem was followed by that of Ore in 1960. In 1984, Fan generalized Dirac's theorem and Ore's theorem as if G is a 2-connected graph of order n and max {d (u),d (v)}≥n/2 for each pair of vertices u and v with d (u,v)=2, then G is hamiltonian. In 1991, Faudree et al proved that if G is a 2-connected graph and, |N (u)∪N (v)|+δ(G)≥n for each pair of nonadjacent vertices u,v∈V(G), then G is hamiltonian. This paper generalizes the above conditions of Dirac, Ore, Fan and Faudree et al in the case of 3-connected graph and proves that if G is a 3-connected graph of order n and max{|N(x)∪ N (y)| +d (u), |N (w)∪N (z)|+d (v)}≥n for every choice of 6 Essential independent vertices, then G is hamiltonian.
基金Supported by the National Natural Science Foundation of China(11871099).
文摘In this note,we show a sharp lower bound of min{Σ_(i=1)^(k)dG(u_(i)):u1u2...uk is a path of(2-)connected G}on its order such that(k-1)-iterated line graphs L^(k-1)(G)are hamiltonian.
