A known result by Jackson Bill is that every 2-connected k-regular graph on at most 3k vertices is Hamiltonian. In this paper,it is proved that every 2-connected k-regular claw-free graph on at most 5k(k≥10)vertices ...A known result by Jackson Bill is that every 2-connected k-regular graph on at most 3k vertices is Hamiltonian. In this paper,it is proved that every 2-connected k-regular claw-free graph on at most 5k(k≥10)vertices is Hamiltonian. Moreover, the bound 5k is best possible. A counterexample of a 2-connected k-regular claw-free non-Hamiltonian graph on 5k+1 vertices is given, and it is conjectured that every 3-connected k-regular claw-free graph on at most 12k-7 vertices is Hamiltonian.展开更多
Many results have been obtained in investigating the existence of Hamiltonian cycles in 2-connected, k-regular graphs, see [3], [1], [4], [6] and [2].We consider only simple graphs here and use standard graph theory n...Many results have been obtained in investigating the existence of Hamiltonian cycles in 2-connected, k-regular graphs, see [3], [1], [4], [6] and [2].We consider only simple graphs here and use standard graph theory notations and terminology. We let V(G) and E(G) denote the vertex set and the edge set of graph G respectively.展开更多
M. Matthews and D. Sumner proved that if G is a 2-connected claw-free graph of order n, then c(G) min{2δb + 4, n}. In this paper, we prove that if G is a,2-connected claw-free graph on n venices, then c(G) min{3δ + ...M. Matthews and D. Sumner proved that if G is a 2-connected claw-free graph of order n, then c(G) min{2δb + 4, n}. In this paper, we prove that if G is a,2-connected claw-free graph on n venices, then c(G) min{3δ + 2, n} or G belongs to one exceptional class of graphs.展开更多
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.展开更多
Alspach提出如下猜想:"设n是奇数并且每个m_1,m_2,…,m_h都是大于等于3而小于等于n的整数.若sum from i=1 to h m_i=n(n-1)/2,则K_n可以分解成圈G_(m_1),G_(m_2),…,G_(m_h)."用记号C(m_1^(n_1)m_2^(n_2)…m_s^(n_s))表示由n_...Alspach提出如下猜想:"设n是奇数并且每个m_1,m_2,…,m_h都是大于等于3而小于等于n的整数.若sum from i=1 to h m_i=n(n-1)/2,则K_n可以分解成圈G_(m_1),G_(m_2),…,G_(m_h)."用记号C(m_1^(n_1)m_2^(n_2)…m_s^(n_s))表示由n_i个m_i长圈,i=1,2,…,s组成的2-正则图.设Γ={C((2m_i)^(n_i)…(2m_s)^(n_s))|i∈[1,s]}.研究了循环(K_v,Γ)-分解的构造方法及其存在性问题,并且证明了Alspach猜想的一些特殊情况.展开更多
A Hamiltonian k-factor is a k-factor containing aHamiltonian cycle.An n/2-critical graph G is a simple graph of order n which satisfies δ(G)≥n/2 and δ(G-e)<n/2 for any edge e∈E(G).Let k≥2 be an integer and G b...A Hamiltonian k-factor is a k-factor containing aHamiltonian cycle.An n/2-critical graph G is a simple graph of order n which satisfies δ(G)≥n/2 and δ(G-e)<n/2 for any edge e∈E(G).Let k≥2 be an integer and G be an n/2-critical graph of even order n≥8k-14.It is shown in this paper that for any given Hamiltonian cycle C except that G-C consists of two components of odd orders when k is odd,G has a k-factor containing C.展开更多
文摘A known result by Jackson Bill is that every 2-connected k-regular graph on at most 3k vertices is Hamiltonian. In this paper,it is proved that every 2-connected k-regular claw-free graph on at most 5k(k≥10)vertices is Hamiltonian. Moreover, the bound 5k is best possible. A counterexample of a 2-connected k-regular claw-free non-Hamiltonian graph on 5k+1 vertices is given, and it is conjectured that every 3-connected k-regular claw-free graph on at most 12k-7 vertices is Hamiltonian.
文摘Many results have been obtained in investigating the existence of Hamiltonian cycles in 2-connected, k-regular graphs, see [3], [1], [4], [6] and [2].We consider only simple graphs here and use standard graph theory notations and terminology. We let V(G) and E(G) denote the vertex set and the edge set of graph G respectively.
文摘M. Matthews and D. Sumner proved that if G is a 2-connected claw-free graph of order n, then c(G) min{2δb + 4, n}. In this paper, we prove that if G is a,2-connected claw-free graph on n venices, then c(G) min{3δ + 2, n} or G belongs to one exceptional class of graphs.
基金The research was supported by NNSF of China(19971027, 10271048) Shanghai Priority Academic Discipline. The research was done while the author was visiting LRI.
基金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.
文摘Alspach提出如下猜想:"设n是奇数并且每个m_1,m_2,…,m_h都是大于等于3而小于等于n的整数.若sum from i=1 to h m_i=n(n-1)/2,则K_n可以分解成圈G_(m_1),G_(m_2),…,G_(m_h)."用记号C(m_1^(n_1)m_2^(n_2)…m_s^(n_s))表示由n_i个m_i长圈,i=1,2,…,s组成的2-正则图.设Γ={C((2m_i)^(n_i)…(2m_s)^(n_s))|i∈[1,s]}.研究了循环(K_v,Γ)-分解的构造方法及其存在性问题,并且证明了Alspach猜想的一些特殊情况.
基金This research is supported partially by the National Natural Science Foundation of China.
文摘A Hamiltonian k-factor is a k-factor containing aHamiltonian cycle.An n/2-critical graph G is a simple graph of order n which satisfies δ(G)≥n/2 and δ(G-e)<n/2 for any edge e∈E(G).Let k≥2 be an integer and G be an n/2-critical graph of even order n≥8k-14.It is shown in this paper that for any given Hamiltonian cycle C except that G-C consists of two components of odd orders when k is odd,G has a k-factor containing C.
