共查询到7条相似文献,搜索用时 15 毫秒
1.
XU Baogang 《系统科学与复杂性》2002,(3)
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.
LIUYan WANGShiying 《系统科学与复杂性》2004,17(1):33-38
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.
HUANG Qiongxiang LIU Xin Department of Mathematics Xinjiang Univerasity Urumchi China 《系统科学与复杂性》1993,(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.
XU Liqiong GUO Xiaofeng 《系统科学与复杂性》2005,18(4):564-569
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.
田丰 《系统科学与复杂性》1991,(4)
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.
FROM MANUFACTURING SCHEDULING TO SUPPLY CHAIN COORDINATION:THE CONTROL OF COMPLEXITY AND UNCERTAINTY
Peter B.LUH 《系统科学与系统工程学报(英文版)》2003,12(3):279-297
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 相似文献