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.展开更多
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.展开更多
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.展开更多
Let G be a simple undirected graph.For any real numberα∈[0,1],Nikiforov defined the A_(α)-matrix of G as A_(α)(G)=αD(G)+(1-α)A(G)in 2017,where A(G)and D(G)are the adjacency matrix and the degree diagonal matrix ...Let G be a simple undirected graph.For any real numberα∈[0,1],Nikiforov defined the A_(α)-matrix of G as A_(α)(G)=αD(G)+(1-α)A(G)in 2017,where A(G)and D(G)are the adjacency matrix and the degree diagonal matrix of G,respectively.In this paper,we obtain a lower bound on the A_(α)-spectral radius of a C_(3)-free graph forα∈[0,1)and a sharp upper bound on the Aα-spectral radius of a C_(3)-free k-cycle graph forα∈[1/2,1).展开更多
基金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.
基金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.
基金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.
基金Supported by the National Natural Science Foundation of China(Grant Nos.12071411,12171222)。
文摘Let G be a simple undirected graph.For any real numberα∈[0,1],Nikiforov defined the A_(α)-matrix of G as A_(α)(G)=αD(G)+(1-α)A(G)in 2017,where A(G)and D(G)are the adjacency matrix and the degree diagonal matrix of G,respectively.In this paper,we obtain a lower bound on the A_(α)-spectral radius of a C_(3)-free graph forα∈[0,1)and a sharp upper bound on the Aα-spectral radius of a C_(3)-free k-cycle graph forα∈[1/2,1).
