Let G be a 2-connected graph of order n(greater than or equal to 3). If I(u,upsilon) greater than or equal to S(u,upsilon) or max {d(u), d(upsilon)} greater than or equal to n/2 for any two vertices u, upsilon at dist...Let G be a 2-connected graph of order n(greater than or equal to 3). If I(u,upsilon) greater than or equal to S(u,upsilon) or max {d(u), d(upsilon)} greater than or equal to n/2 for any two vertices u, upsilon at distance two in an induced subgraph K-1,K-3,3 or P-3 of G, then G is hamiltonian. Here I(u,upsilon) = \N(u) boolean AND N(upsilon)\, S(u,nu) denotes the number of edges of maximum star containing u, upsilon as an induced subgraph in G.展开更多
Let G be a circuit graph of a connected matroid. P. Li and G. Liu [Comput. Math. Appl., 2008, 55： 654-659] proved that G has a Hamilton cycle including e and another Hamilton cycle excluding e for any edge e of G if ...Let G be a circuit graph of a connected matroid. P. Li and G. Liu [Comput. Math. Appl., 2008, 55： 654-659] proved that G has a Hamilton cycle including e and another Hamilton cycle excluding e for any edge e of G if G has at least four vertices. This paper proves that G has a Hamilton cycle including e and excluding e＇ for any two edges e and e＇ of G if G has at least five vertices. This result is best possible in some sense. An open problem is proposed in the end of this paper.展开更多
We discuss k-factors and Hamiltonian Graphs in graph theory. We prove a general version of the conjecture by R. Haggkvist; as a result, we prove two extended versions of two well-known theorems due to O. Ore and B. Ja...We discuss k-factors and Hamiltonian Graphs in graph theory. We prove a general version of the conjecture by R. Haggkvist; as a result, we prove two extended versions of two well-known theorems due to O. Ore and B. Jachson, respectively.展开更多
A k-cycle system of order v with index A, denoted by CS（v, k, λ）, is a collection A of k-cycles （blocks） of Kv such that each edge in Kv appears in exactly λ blocks of A. A large set of CS（v, k, λ）s is a part...A k-cycle system of order v with index A, denoted by CS（v, k, λ）, is a collection A of k-cycles （blocks） of Kv such that each edge in Kv appears in exactly λ blocks of A. A large set of CS（v, k, λ）s is a partition of the set of all k-cycles of Kv into CS（v, k, λ）s, and is denoted by LCS（v, k, λ）. A （v - 1）-cycle in K, is called almost Hamilton. The completion of the existence problem for LCS（v, v- 1,λ） depends only on one case： all v ≥ 4 for λ=2. In this paper, it is shown that there exists an LCS（v,v - 1,2） for all v ≡ 2 （mod 4）, v ≥ 6.展开更多
This paper shows that if G is a connected graph of order n such that <(sigma(2)(G))over bar> > 2(n/5 - 1) and L(G) is hamiltonian, then, for n greater than or equal to 43, L(G) is pancyclic. Using the result ...This paper shows that if G is a connected graph of order n such that <(sigma(2)(G))over bar> > 2(n/5 - 1) and L(G) is hamiltonian, then, for n greater than or equal to 43, L(G) is pancyclic. Using the result of Veldman([8]) this result settles the conjecture of Benhocine, et.al([1]): Let G be a connected almost bridgeless graph of order n such that <(sigma(2)(G))over bar> > 2(n/5 - 1). If n is sufficintly large, L(G) is pancyclic.展开更多
In 1989, Zhu, Li and Deng introduced the definition of implicit degree of a vertex v in a graph G, denoted by id（v）. In this paper, we prove that if G is a 2-connected graph of order n such that id（u） ＋ id（v） ...In 1989, Zhu, Li and Deng introduced the definition of implicit degree of a vertex v in a graph G, denoted by id（v）. In this paper, we prove that if G is a 2-connected graph of order n such that id（u） ＋ id（v） ≥ n for each pair of nonadjacent vertices u and v in G, then G is pancyclic unless G is bipartite, or else n = 4r, r ≥ 2 and G is isomorphic to F4r .展开更多
文摘Let G be a 2-connected graph of order n(greater than or equal to 3). If I(u,upsilon) greater than or equal to S(u,upsilon) or max {d(u), d(upsilon)} greater than or equal to n/2 for any two vertices u, upsilon at distance two in an induced subgraph K-1,K-3,3 or P-3 of G, then G is hamiltonian. Here I(u,upsilon) = \N(u) boolean AND N(upsilon)\, S(u,nu) denotes the number of edges of maximum star containing u, upsilon as an induced subgraph in G.
基金The authors would like to thank the referees for providing some very helpful suggestions for revising this paper. This work was supported by the National Natural Science Foundation of China （Grant No. 61070230）.
文摘Let G be a circuit graph of a connected matroid. P. Li and G. Liu [Comput. Math. Appl., 2008, 55： 654-659] proved that G has a Hamilton cycle including e and another Hamilton cycle excluding e for any edge e of G if G has at least four vertices. This paper proves that G has a Hamilton cycle including e and excluding e＇ for any two edges e and e＇ of G if G has at least five vertices. This result is best possible in some sense. An open problem is proposed in the end of this paper.
基金supported by the Key Laboratory of Power System,Tsinghua University
文摘We discuss k-factors and Hamiltonian Graphs in graph theory. We prove a general version of the conjecture by R. Haggkvist; as a result, we prove two extended versions of two well-known theorems due to O. Ore and B. Jachson, respectively.
基金Supported in part by the National Natural Science Foundation of China(No.10901051,11201143)the Fundamental Research Funds for the Central Universities(No.2016MS66)the Co-construction Project of Bejing Municipal Commission of Education
文摘A k-cycle system of order v with index A, denoted by CS（v, k, λ）, is a collection A of k-cycles （blocks） of Kv such that each edge in Kv appears in exactly λ blocks of A. A large set of CS（v, k, λ）s is a partition of the set of all k-cycles of Kv into CS（v, k, λ）s, and is denoted by LCS（v, k, λ）. A （v - 1）-cycle in K, is called almost Hamilton. The completion of the existence problem for LCS（v, v- 1,λ） depends only on one case： all v ≥ 4 for λ=2. In this paper, it is shown that there exists an LCS（v,v - 1,2） for all v ≡ 2 （mod 4）, v ≥ 6.
文摘This paper shows that if G is a connected graph of order n such that <(sigma(2)(G))over bar> > 2(n/5 - 1) and L(G) is hamiltonian, then, for n greater than or equal to 43, L(G) is pancyclic. Using the result of Veldman([8]) this result settles the conjecture of Benhocine, et.al([1]): Let G be a connected almost bridgeless graph of order n such that <(sigma(2)(G))over bar> > 2(n/5 - 1). If n is sufficintly large, L(G) is pancyclic.
文摘In 1989, Zhu, Li and Deng introduced the definition of implicit degree of a vertex v in a graph G, denoted by id（v）. In this paper, we prove that if G is a 2-connected graph of order n such that id（u） ＋ id（v） ≥ n for each pair of nonadjacent vertices u and v in G, then G is pancyclic unless G is bipartite, or else n = 4r, r ≥ 2 and G is isomorphic to F4r .
