On the selection of subdivision directions in interval branch-and-bound methods for global optimization

This paper investigates the influence of the interval subdivision selection rule on the convergence of interval branch-and-bound algorithms for global optimization. For the class of rules that allows convergence, we study the effects of the rules on a model algorithm with special list ordering. Four different rules are investigated in theory and in practice. A wide spectrum of test problems is used for numerical tests indicating that there are substantial differences between the rules with respect to the required CPU time, the number of function and derivative evaluations, and the necessary storage space. Two rules can provide considerable improvements in efficiency for our model algorithm.The work has been supported by the Grants OTKA 2879/1991, and MKM 414/1994.     

Contractibility techniques as a closure concept

We introduce a closure concept in the class of line graphs and claw‐free graphs based on contractibility of certain subgraphs in the line graph preimage. The closure can be considered as a common generalization and strengthening of the reduction techniques of Catlin and Veldman and of the closure concept introduced by the first author. We show that the closure is uniquely determined and the closure operation preserves the circumference of the graph. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 37–48, 2003     

关于k—覆盖图的一些新结果

本文给出了一个图G是k-覆盖图的若干充分条件．     

图的下测地数和上测地数

对于图G(或有向图D)内的任意两点u和v,u—v测地线是指在u和v之间(或从u到v)的最短路．I(u,v)表示位于u—v测地线上所有点的集合,对于S(?)V(G)(或V(D)),I(S)表示所有I(u,v)的并,这里u,v∈S．G(或D)的测地数g(G)(或g(D))是使I(S)=V(G)(或I(S)=V(D))的点集S的最小基数．G的下测地数g~-(G)=min{g(D)：D是G的定向图},G的上测地数g~ (G)=max{g(D)：D是G的定向图}．对于u∈V(G)和v∈V(H),G_u H_v表示在u和v之间加一条边所得的图．本文主要研究图G_u H_v的测地数和上(下)测地数．     

The growth of solutions of linear differential equations with coefficients of iterated order in the unit disc

In this paper, we give the definition of iterated order to classify functions of fast growth in the unit disc, and investigate the growth of solutions of linear differential equations with analytic coefficients of iterated order in the unit disc. We obtain several results concerning the iterated order of solutions.     

Construction for bicritical graphs and k-extendable bipartite graphs

A graph G is said to be bicritical if G-u-v has a perfect matching for every choice of a pair of points u and v. Bicritical graphs play a central role in decomposition theory of elementary graphs with respect to perfect matchings. As Plummer pointed out many times, the structure of bicritical graphs is far from completely understood. This paper presents a concise structure characterization on bicritical graphs in terms of factor-critical graphs and transversals of hypergraphs. A connected graph G with at least 2k+2 points is said to be k-extendable if it contains a matching of k lines and every such matching is contained in a perfect matching. A structure characterization for k-extendable bipartite graphs is given in a recursive way. Furthermore, this paper presents an O(mn) algorithm for determining the extendability of a bipartite graph G, the maximum integer k such that G is k-extendable, where n is the number of points and m is the number of lines in G.     

关于有限域上一类方程零点个数的估计

By establishing the connection between graph colouring and the solution of some equation systems in finite fields, we obtain some formulas to the number of solutions of some equation systems in finite fields, in terms of chromatic polynomial of a graph.     

E -Theoretic Duality for Higher Rank Graph Algebras

We prove that there is a Poincaré type duality in E-theory between higher rank graph algebras associated with a higher rank graph and its opposite correspondent. We obtain an r-duality, that is the fundamental classes are in E^r. The basic tools are a higher rank Fock space and higher rank Toeplitz algebra which has a more interesting ideal structure than in the rank 1 case. The K-homology fundamental class is given by an r-fold exact sequence whereas the K-theory fundamental class is given by a homomorphism. The E-theoretic products are essentially pull-backs so that the computation is done at the level of exact sequences. Mathematics Subject Classification (2000): 46L80.     

Halving Steiner 2-designs

A Steiner 2-design S(2,k,v) is said to be halvable if the block set can be partitioned into two isomorphic sets. This is equivalent to an edge-disjoint decomposition of a self-complementary graph G on v vertices into K_ks. The obvious necessary condition of those orders v for which there exists a halvable S(2,k,v) is that v admits the existence of an S(2,k,v) with an even number of blocks. In this paper, we give an asymptotic solution for various block sizes. We prove that for any k?5 or any Mersenne prime k, there is a constant number v₀ such that if v>v₀ and v satisfies the above necessary condition, then there exists a halvable S(2,k,v). We also show that a halvable S(2,2ⁿ,v) exists for over a half of possible orders. Some recursive constructions generating infinitely many new halvable Steiner 2-designs are also presented.