For a graph G, we denote by p(G) and c(G) the number of vertices of a longest path and a longest cycle in G, respectively. For a vertex v in G, id(v) denotes the implicit degree of v. In this paper, we obtain th...For a graph G, we denote by p(G) and c(G) the number of vertices of a longest path and a longest cycle in G, respectively. For a vertex v in G, id(v) denotes the implicit degree of v. In this paper, we obtain that if G is a 2-connected graph on n vertices such that the implicit degree sum of any three independent vertices is at least n + 1, then either G contains a hamiltonian path, or c(G) 〉 p(G) - 1.展开更多
In 2005,Flandrin et al.proved that if G is a k-connected graph of order n and V(G)=X1∪X2∪···∪Xk such that d(x)+d(y)≥n for each pair of nonadjacent vertices x,y∈Xi and each i with i=1,2,··...In 2005,Flandrin et al.proved that if G is a k-connected graph of order n and V(G)=X1∪X2∪···∪Xk such that d(x)+d(y)≥n for each pair of nonadjacent vertices x,y∈Xi and each i with i=1,2,···,k,then G is hamiltonian.In order to get more sufficient conditions for hamiltonicity of graphs,Zhu,Li and Deng proposed the definitions of two kinds of implicit degree of a vertex v,denoted by id1(v)and id2(v),respectively.In this paper,we are going to prove that if G is a k-connected graph of order n and V(G)=X1∪X2∪···∪Xk such that id2(x)+id2(y)≥n for each pair of nonadjacent vertices x,y∈Xi and each i with i=1,2,···,k,then G is hamiltonian.展开更多
基金supported by the National Natural Science Foundation of China(Grant No.11501322)the Postdoctoral Science Foundation of China(Grant No.2015M571999)the Natural Science Foundation of Shandong Province(Grant No.ZR2014AP002)
文摘For a graph G, we denote by p(G) and c(G) the number of vertices of a longest path and a longest cycle in G, respectively. For a vertex v in G, id(v) denotes the implicit degree of v. In this paper, we obtain that if G is a 2-connected graph on n vertices such that the implicit degree sum of any three independent vertices is at least n + 1, then either G contains a hamiltonian path, or c(G) 〉 p(G) - 1.
基金supported by the National Natural Science Foundation of China (No.11501322)Scientific Research Foundation for Doctors in Qufu Normal University (No. 2012015)Natural Science Foundation of Qufu Normal University (No.xkj201415)
文摘In 2005,Flandrin et al.proved that if G is a k-connected graph of order n and V(G)=X1∪X2∪···∪Xk such that d(x)+d(y)≥n for each pair of nonadjacent vertices x,y∈Xi and each i with i=1,2,···,k,then G is hamiltonian.In order to get more sufficient conditions for hamiltonicity of graphs,Zhu,Li and Deng proposed the definitions of two kinds of implicit degree of a vertex v,denoted by id1(v)and id2(v),respectively.In this paper,we are going to prove that if G is a k-connected graph of order n and V(G)=X1∪X2∪···∪Xk such that id2(x)+id2(y)≥n for each pair of nonadjacent vertices x,y∈Xi and each i with i=1,2,···,k,then G is hamiltonian.