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.     

关于三次图边可重构问题的注记

对δ（Ｇ）≥８的连续三次图Ｇ是边可重构的定理给出了一个简单证明。此外还证明了，当δ（Ｇ）＝７，γ（Ｇ）≤８２以及δ（Ｇ）＝６，γ（Ｇ）≤１７时，连续三次图Ｇ是边可重构的     

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 的一个赛程安排方案     

���������������������͵�������

??In this paper, by applying the moment inequality for asymptotically almost negatively associated (AANA, in short) random sequence and truncated method, the equivalent conditions of complete moment convergence of the maximum partial for weighted sums of AANA random variables are obtained without assumptions of identical distribution, which generalize and improve the corresponding ones of{15},{16} and {17}, respectively.     

The valuations of the near hexagons related to the Witt designs S(5,6,12) and S(5,8,24)

Valuations of dense near polygons were introduced in 16 . In the present paper, we classify all valuations of the near hexagons ??₁ and ??₂, which are related to the respective Witt designs S(5,6,12) and S(5,8,24). Using these classifications, we prove that if a dense near polygon S contains a hex H isomorphic to ??₁ or ??₂, then H is classical in S. We will use this result to determine all dense near octagons that contain a hex isomorphic to ??₁ or ??₂. As a by‐product, we obtain a purely geometrical proof for the nonexistence of regular near 2d‐gons, d ≥ 4, whose parameters s, t, t_i (0 ≤ i ≤ d) satisfy (s, t₂, t₃) = (2, 1, 11) or (2, 2, 14). The nonexistence of these regular near polygons can also be shown with the aid of eigenvalue techniques. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 214–228, 2006     

On disjoint configurations in infinite graphs

For a graph A and a positive integer n, let nA denote the union of n disjoint copies of A; similarly, the union of ?₀ disjoint copies of A is referred to as ?₀A. It is shown that there exist (connected) graphs A and G such that nA is a minor of G for all n??, but ?₀A is not a minor of G. This supplements previous examples showing that analogous statements are true if, instead of minors, isomorphic embeddings or topological minors are considered. The construction of A and G is based on the fact that there exist (infinite) graphs G₁, G₂,… such that G_i is not a minor of G_j for all i ≠ j. In contrast to previous examples concerning isomorphic embeddings and topological minors, the graphs A and G presented here are not locally finite. The following conjecture is suggested: for each locally finite connected graph A and each graph G, if nA is a minor of G for all n ? ?, then ?₀A is a minor of G, too. If true, this would be a far‐reaching generalization of a classical result of R. Halin on families of disjoint one‐way infinite paths in graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 222–229, 2002; DOI 10.1002/jgt.10016