Let ARDkCS（v） denote an almost resolvable directed k-cycle system of order v. It is clear that a necessary condition for the existence of an ARDkCS（v） is v=1（mod k）. For k：3,4,5 and 6, the existence of an ARDk...Let ARDkCS（v） denote an almost resolvable directed k-cycle system of order v. It is clear that a necessary condition for the existence of an ARDkCS（v） is v=1（mod k）. For k：3,4,5 and 6, the existence of an ARDkCS （v） had been completely solved. This paper shows that there exists an ARD7CS（v） if and only if v≡1 （rood 7） and v≥8.展开更多
A graph G has the hourglass property if every induced hourglass S（a tree with a degree sequence 22224） contains two non-adjacent vertices which have a common neighbor in G-V（S）.For an integer k≥4,a graph G has th...A graph G has the hourglass property if every induced hourglass S（a tree with a degree sequence 22224） contains two non-adjacent vertices which have a common neighbor in G-V（S）.For an integer k≥4,a graph G has the single k-cycle property if every edge of G,which does not lie in a triangle,lies in a cycle C of order at most k such that C has at least「｜V（C） /2」 edges which do not lie in a triangle,and they are not adjacent.In this paper,we show that every hourglass-free claw-free graph G of δ（G） ≥3 with the single 7-cycle property is Hamiltonian and is best possible;we also show that every claw-free graph G of δ（G） ≥3 with the hourglass property and with single 6-cycle property is Hamiltonian.展开更多
Staggered formalism of lattice fermion can be cast into a form of direct product K-cycle in noncommutative geometry. We prove the correspondence between this staggered K-cycle and a canonically defined K-cycle for fin...Staggered formalism of lattice fermion can be cast into a form of direct product K-cycle in noncommutative geometry. We prove the correspondence between this staggered K-cycle and a canonically defined K-cycle for finitely generated Abelian groups where a lattice appears as a special case.展开更多
Given a weighted graph G=(V,E)with weight w:E→Z+,a k-cycle transversal is an edge subset A of E such that G−A has no k-cycle.The minimum weight of kcycle transversal is the weighted transversal number on k-cycle,deno...Given a weighted graph G=(V,E)with weight w:E→Z+,a k-cycle transversal is an edge subset A of E such that G−A has no k-cycle.The minimum weight of kcycle transversal is the weighted transversal number on k-cycle,denoted byτk(Gw).In this paper,we design a(k−1/2)-approximation algorithm for the weighted transversal number on k-cycle when k is odd.Given a weighted graph G=(V,E)with weight w:E→Z+,a k-clique transversal is an edge subset A of E such that G−A has no k-clique.The minimum weight of k-clique transversal is the weighted transversal number on k-clique,denoted byτapproximation algorithm for the weighted transversal number on k(Gw).In this paper,we design a(k2−k−1)/2-k-clique.Last,we discuss the relationship between k-clique covering and k-clique packing in complete graph Kn.展开更多
We study the number of k-cycles in a random graph G（n, p）. We estimate the probability that a random graph contains more k-cycles than expected. In this case, the usual martingale inequality with bounded difference ...We study the number of k-cycles in a random graph G（n, p）. We estimate the probability that a random graph contains more k-cycles than expected. In this case, the usual martingale inequality with bounded difference is not effective. By construct- ing a variable that approximates to the number of k-cycles in a random graph and using a new and extensive martingale inequality, we get the results in this paper.展开更多
基金Natural Science Research Leading Item ofJiangsu (No.04 DJ110144) Natural Out-standing Younger Science Foundation(No.60225007)and Postdoctoral ScienceFoundation of China(No.20020248024)
文摘Let ARDkCS（v） denote an almost resolvable directed k-cycle system of order v. It is clear that a necessary condition for the existence of an ARDkCS（v） is v=1（mod k）. For k：3,4,5 and 6, the existence of an ARDkCS （v） had been completely solved. This paper shows that there exists an ARD7CS（v） if and only if v≡1 （rood 7） and v≥8.
基金Supported by the National Natural Science Foundation of China(11071016 and 11171129)the Beijing Natural Science Foundation(1102015)
文摘A graph G has the hourglass property if every induced hourglass S（a tree with a degree sequence 22224） contains two non-adjacent vertices which have a common neighbor in G-V（S）.For an integer k≥4,a graph G has the single k-cycle property if every edge of G,which does not lie in a triangle,lies in a cycle C of order at most k such that C has at least「｜V（C） /2」 edges which do not lie in a triangle,and they are not adjacent.In this paper,we show that every hourglass-free claw-free graph G of δ（G） ≥3 with the single 7-cycle property is Hamiltonian and is best possible;we also show that every claw-free graph G of δ（G） ≥3 with the hourglass property and with single 6-cycle property is Hamiltonian.
文摘Staggered formalism of lattice fermion can be cast into a form of direct product K-cycle in noncommutative geometry. We prove the correspondence between this staggered K-cycle and a canonically defined K-cycle for finitely generated Abelian groups where a lattice appears as a special case.
基金the National Natural Science Foundation of China(No.11901605)the disciplinary funding of Central University of Finance and Economics.
文摘Given a weighted graph G=(V,E)with weight w:E→Z+,a k-cycle transversal is an edge subset A of E such that G−A has no k-cycle.The minimum weight of kcycle transversal is the weighted transversal number on k-cycle,denoted byτk(Gw).In this paper,we design a(k−1/2)-approximation algorithm for the weighted transversal number on k-cycle when k is odd.Given a weighted graph G=(V,E)with weight w:E→Z+,a k-clique transversal is an edge subset A of E such that G−A has no k-clique.The minimum weight of k-clique transversal is the weighted transversal number on k-clique,denoted byτapproximation algorithm for the weighted transversal number on k(Gw).In this paper,we design a(k2−k−1)/2-k-clique.Last,we discuss the relationship between k-clique covering and k-clique packing in complete graph Kn.
基金Supported by the National Natural Science Foundation of China (10571139)
文摘We study the number of k-cycles in a random graph G（n, p）. We estimate the probability that a random graph contains more k-cycles than expected. In this case, the usual martingale inequality with bounded difference is not effective. By construct- ing a variable that approximates to the number of k-cycles in a random graph and using a new and extensive martingale inequality, we get the results in this paper.
