一类几乎最优循环图{C_p(m,m+1,p/a)}

本文比较了循环图类{c_p(n_1,…,n_p)}和{c-p(n_1…,n_p,p/α)}的直径下界。对于p和α满足一定条件的循环图类{c_p(n_1,n_2,p/α)},本文给出了达到或几乎达到此图类直径下界的一类几乎最优循环图{c_p(m,m+1,p/α)}。     

Combinatorial Optimization by Dynamic Contraction

A heuristic optimization methodology, Dynamic Contraction (DC), is introduced as an approach for solving a wide variety of hard combinatorial problems. Contraction is an operation that maps an instance of a problem to a smaller instance of the same problem. DC is an iterative improvement strategy that relies on contraction as a mechanism for escaping local minima. As a byproduct of contraction, efficiency is improved due to a reduction of problem size. Effectiveness of DC is shown through simple applications to two classical combinatorial problems: The graph bisection problem and the traveling salesman problem.     

A graph theory approach to subcontracting, machine duplication and intercell moves in cellular manufacturing

We address in this paper the problem of finding an optimal strategy for dealing with bottleneck machines and bottleneck parts in the cell formation process in group technology. Three types of economic decisions are considered: subcontracting, machine duplication and intercell moves. The problem is formulated as a minimum weighted node covering problem in a hypergraph, and we show that it can be solved in polynomial time by finding a maximum weighted stable set in a bipartite graph. We extend this result to cellular manufacturing systems in which the sequence of operations of each part is known in advance.     

Some Recent Progress and Applications in Graph Minor Theory

In the core of the seminal Graph Minor Theory of Robertson and Seymour lies a powerful theorem capturing the ``rough' structure of graphs excluding a fixed minor. This result was used to prove Wagner's Conjecture that finite graphs are well-quasi-ordered under the graph minor relation. Recently, a number of beautiful results that use this structural result have appeared. Some of these along with some other recent advances on graph minors are surveyed. Research partly supported by Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research, Grant number 16740044, by Sumitomo Foundation, by C & C Foundation and by Inoue Research Award for Young Scientists Supported in part by the Research Grant P1–0297 and by the CRC program On leave from: IMFM & FMF, Department of Mathematics, University of Ljubljana, Ljubljana, Slovenia     

Gk^d图的平面性和平面图的色数

利用欧拉公式研究了Gdk图的平面性,获得了一个重要定理,并由此得到了关于平面图色数的一个结论.     

Clustering of spectra and fractals of regular graphs

We exhibit a characteristic structure of the class of all regular graphs of degree d that stems from the spectra of their adjacency matrices. The structure has a fractal threadlike appearance. Points with coordinates given by the mean and variance of the exponentials of graph eigenvalues cluster around a line segment that we call a filar. Zooming-in reveals that this cluster splits into smaller segments (filars) labeled by the number of triangles in graphs. Further zooming-in shows that the smaller filars split into subfilars labeled by the number of quadrangles in graphs, etc. We call this fractal structure, discovered in a numerical experiment, a multifilar structure. We also provide a mathematical explanation of this phenomenon based on the Ihara-Selberg trace formula, and compute the coordinates and slopes of all filars in terms of Bessel functions of the first kind.     

极值图论与度序列

本文简要概述极值图论与度序列的最新研究进展，同时提出了一些有待进一步解决的问题和猜想．     

单循环赛赛程安排的一个图论方法

利用图论的边着色理论建立了一个赛程安排的数学模型 .首先建立 n支球队与完全图 Kn的 n个顶点间的一一对应 ,把球队 Ai和 Aj间的比赛关系抽象成 Kn的顶点 i和 j间的边 ( i,j) .然后分别构造出了图K2 m- 1和 K2 m的正常 2 m-1边着色 .从而给出了各球队每两场比赛间得到的休整时间最均等 ,休整的间隔场次数达到上限值 n2 的一个赛程安排方案     

纯量反馈系统同时强镇定的充分条件

一个稳定的补偿器可同时镇定n个对象(同时强镇定)等价于一个补偿器(不一定稳定)同时镇定n 1个对象(同时镇定)．两个以上对象的同时强镇定和三个以上对象的伺时镇定是线性系统中一个急待解决的公开问题．文中所作的基本假定是所有的对象具有相同的简单不稳定零点，在此条件下给出了n个对象同时强镇定的一个充分条件．当仅有一个不稳定零点时．容易检验是否同时强镇定，否则仅需确定n个对象的不稳定零点并且判定由不稳定零点导出一个相应矩阵是正定的，就能判定n个对象同时强镇定．因此是一个易于检验的充分条件．文章同时给出了n个对象同时强镇定的算法，丰富了同时强镇定的充分条件．     

An unknotting theorem for delta and sharp edge‐homotopy

Two spatial embeddings of a graph are said to be delta (resp. sharp) edge‐homotopic if they are transformed into each other by self delta (resp. sharp) moves and ambient isotopies. We show that any two spatial embeddings of a graph are delta (resp. sharp) edge‐homotopic if and only if the graph does not contain a subgraph which is homeomorphic to the theta graph or the disjoint union of two 1‐spheres, or equivalently G is homeomorphic to a bouquet. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)