首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到7条相似文献,搜索用时 15 毫秒
1.
Hajos' conjecture asserts that a simple eulerian graph on n vertices can be decomposed into at most n-1/2 circuits. In this paper, we propose a new conjecture which is equivalent to Hajos' conjecture, and show that to prove Hajos' conjecture, it is sufficient to prove this new conjecture for 3-connected graphs. Furthermore, a special 3-cut is considered also.  相似文献   

2.
The maximum matching graph of a graph has a vertex for each maximummatching and an edge for each pair of maximum matchings which differ by exactly oneedge. In this paper, we prove that the connectivity of maximum matching graph of abipartite graph is equal to its minimum degree.  相似文献   

3.
In this paper we obtain the necessary and sufficient condition for the connec-tivity of the Cayley color graphs or the Cayley graphs to be equal to their minimum degree.The sharp lower bounds of connectivity of Cayley color graphs and the Cayley graphs arealso obtained. Our results generalize the previous results obtained in [1] to [3].  相似文献   

4.
A. Kaneko and K. Ota proved that for a minimally (n, λ)-connected graph G, if |G| = p ≥ 3n - 1, then e(G) ≤ nλ(|G| - n); and if e(G) = nλ(|G| - n), then G is isomorphic to the graph Kn^λ,p-n which is obtained from the complete bipartite graph Kn,p-n by replacing each edge with A multiple edges; if 3n - 1 ≥ |G}≥ n + 1, then e(G) ≤λ(|G| + n)^2/8. In this paper, we determine all the minimally (n, λ)-connected graphs with order p and the maximum size λ(p+n)^2/8 for 3n- 1 ≥ p ≥ n+ 1 for 3n-1≥p≥n+1.  相似文献   

5.
ANOTEONTHEPAPER"ONTHECONNECTIVITYOFCAYLEYCOLORGRAPHS"¥MENGJixiang;HUANGQiongxiang(DepartmentofMathematics,XiniiangUniversity,...  相似文献   

6.
Combining forbidden subgraphs with degree restrictions and neighborhood unionrestrictions,respectively,we prove the following results:(1) Let G be a 2-connected graph of order n,and 3≤c≤n.If for each induced subgraphL of order four of G(?)|V_1(L)∩S_c|≥2 if L≌K_(1,3),and |V(L)∩S_c|≥1 if L≌P_4,then thecircumference of G is at least c,where V_1(L)is the set of vertices with degree 1 of L,S_c isthe set of vertices with degree at least c/2 of G and P_4 is a path of order 4.(2) Let G be a 2-connected graph of order n,and n≥s+2.If for each induced subgraphL of G isomorphic to K_(1,3)or P_4,d_L(u,v)=2(?)|N(u)∪N(v)|≥s,then the circumferencec (G) of G is at least s+2.Moreover,if n≥s+3 and s is odd,then c(G)≥s+3.  相似文献   

7.
With time-based competition and rapid technology advancements, effective manufacturingscheduling and supply chain coordination are critical to quickly respond to changing marketconditions. These problems, however, are difficult in view of inherent complexity and variousuncertainties involved. Based on a series of results by the authors, decomposition and coordination byusing Lagrangian relaxation is identified in this paper as an effective way to control complexity anduncertainty.A manufacturing scheduling problem is first formulated within the job shop context withuncertain order arrivals, processing times, due dates, and part priorities as a separable optimizationproblem. A solution methodology that combines Lagrangian relaxation, stochastic dynamicprogramming, and heuristics is developed. Method improvements to effectively solve large problemsare also highlighted. To extend manufacturing scheduling within a factory to coordinate autonomicmembers across chains of suppliers, a decentralized supply chai  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号