变更图的直径

P(t,n)和C(t,n)分别表示在阶为n的路和圈中添加t条边后得到的图的最小直径；f(t,k)表示从直径为k的图中删去t条边后得到的连通图的最大直径．这篇文章证明了t≥4且n≥5时,P(t,n)≤(n-8)/(t 1) 3；若t为奇数,则C(t,n)≤(n-8)/(t 1) 3；若t为偶数,则C(t,n)≤(n-7)/(t 2) 3．特别地,「(n-1)/5」≤P(4,n)≤「(n 3)/5」,「n/4」-1≤C(3,n)≤「n/4」．最后,证明了：若k≥3且为奇数,则f(t,k)≥(t 1)k-2t 4．这些改进了某些已知结果．     

THE PRIMAL—DUAL POTENTIAL REDUCTION ALGORITHM FOR POSITIVE SEMI—DEFINITE PROGRAMMING

In this paper we introduce a primal-dual potential reduction algorithm for positive semi-definite programming. Using the symetric preserving scalings for both primal and dual interior matrices, we can construct an algorithm which is very similar to the primal-dual potential reduction algorithm of Huang and Kortanek [6] for linear programming. The complexity of the algorithm is either O(nlog(X0 · S0/ε) or O(nlog(X0· S0/ε) depends on the value of ρ in the primal-dual potential function, where X0 and S0 is the initial interior matrices of the positive semi-definite programming.     

关于图的星色数的一点注记

A star coloring of an undirected graph G is a proper coloring of G such that no path of length 3 in G is bicolored.The star chromatic number of an undirected graph G,denoted by χs(G),is the smallest integer k for which G admits a star coloring with k colors.In this paper,we show that if G is a graph with maximum degree △,then χs(G) ≤ [7△3/2],which gets better bound than those of Fertin,Raspaud and Reed.     

线性过程关于大数律的精确渐近性

该文主要讨论的是滑线性过程 $X_k=\sum\limits_{i=-\infty}^\infty a_{i+k}\varepsilon_i$,其中 $\{\varepsilon_i; -\infty$\varphi$ -混合或负相伴随机变量序列,$\{a_i;-\inftyp$, 若 $E|\varepsilon_1|^r<\infty$$\lim_{\epsilon\searrow 0}\epsilon^{2(r-p)/(2-p)}\sum\limits_{n=1}^\infty n^{r/p-2}P\{|S_n|\geq \epsilonn^{1/p}\}=\frac{p}{r-p}E|Z|^{2(r-p)/(2-p)},$ 其中 $Z$ 是服从均值为零,方差为 $\tau^2=\sigma^2\cdot(\sum\limits_{i=-\infty}^\infty a_i)^2$的正态分布.     

最大度大于等于7的平面图的线性荫度

图的染色问题在组合优化、计算机科学和Hessians矩阵的网络计算等方面具有非常重要的应用。其中图的染色中有一种重要的染色——线性荫度,它是一种非正常的边染色,即在简单无向图中,它的边可以分割成线性森林的最小数量。研究最大度$\bigtriangleup（G）\geq7$的平面图$G$的线性荫度,证明了对于两个固定的整数$i$,$j\in\{5,6,7\}$,如果图$G$中不存在相邻的含弦$i$,$j$-圈,则图$G$的线性荫度为$\lceil\frac\bigtriangleup2\rceil$。     

Primal-dual interior-point algorithm for semidefinite optimization based on a new kernel function with trigonometric barrier term

In this paper we propose primal-dual interior-point algorithms for semidefinite optimization problems based on a new kernel function with a trigonometric barrier term. We show that the iteration bounds are $O(\sqrt{n}\log(\frac{n}{\epsilon}))$ for small-update methods and $O(n^{\frac{3}{4}}\log(\frac{n}{\epsilon}))$ for large-update, respectively. The resulting bound is better than the classical kernel function. For small-update, the iteration complexity is the best known bound for such methods.     

逼近已知函数微商的广义Lanczos算法

给出逼近已知函数微商的广义Lanczos 算法, 构造了一列逼近算子$D_{h}^{n}$以提高稳定近似解的收敛速率. 当$n=2$时, 逼近精度达到$O(\delta^{6 \over 7})$, 而对一般的自然数$n$逼近精度为$O(\delta^{\frac{2n+2}{2n+3}})$, 这里$\delta$是近似函数的误差界.     

最大度与最小度相差不超过2的图的平衡judicious划分

图G的顶点集V(G)的一个二部划分V_1和V_2叫做平衡二部划分,如果||V_1|-|V_2||≤1成立.Bollobas和Scott猜想:每一个有m条边且最小度不小于2的图,都存在一个平衡二部划分V_1,V_2,使得max{e(V_1),e(V_2)}≤m/3,此处e(V_i)表示两顶点都在V_i(i=1,2)中的边的条数.他们证明了这个猜想对正则图(即△(G)=δ(G))成立.颜娟和许宝刚证明了每个(k,k-1)-双正则图(即△(G)-δ(G)≤1)存在一个平衡二部划分V_1,V_2,使得每一顶点集的导出子图包含大约m/4条边.这里把该结论推广到最大度和最小度相差不超过2的图G.     

Relationship Between the Stiffly Weighted Pseudoinverse and Multi-Level Constrained Rseudoinverse

It is known that for a given matrix A of rank r, and a set D of positive diagonal matrices, supw∈D‖（W^1/2A) W^1/2‖ = (miniσ (A^(i))^-1, in which (A^(i) is a submatrix of A formed with r = (rank(A)) rows of A, such that (A^(i) has full row rank r. In many practical applications this value is too large to be used. In this paper we consider the case that both A and W(∈D) are fixed with W severely stiff. We show that in this case the weighted pseudoinverse (W^1/2‖A) W^1/2‖ is close to a multilevel constrained weighted pseudoinverse therefore ‖(W^1/2A) W^1/‖2 is uniformly bounded.We also prove that in this case the solution set the stiffly weighted least squares problem is close to that of corresponding multi-level constrained least squares problem.     

几种特殊结构全光网中多播路由的波长分配算法

研究全光WDM网络中多播请求的路由与波长分配问题.给定网络拓扑和一组多播通信请求,要求对其进行路由和波长分配,满足波长连续性和波长无冲突约束,使得所用的波长总数最少.就几类特殊网络进行了研究.首先对二分树网络进行了研究,此时问题是多项式时间可求解的.其次对树网络进行了讨论,证明了即使是星网络,问题也不存在近似比小于m1/2-ρ(0＜ρ＜1))的近似算法,除非NP=ZPP,这里m是星图的边数.随后给出了近似比为(√m 1)(log r/√m 1 1)的近似算法,此结果对一般图也成立.最后考虑了环网和树环网,给出了近似比为3.6和2△的近似算法,这里△是图的最大度.     

LIMIT CYCLES OF THE GENERALIZED POLYNOMIAL LINARD DIFFERENTIAL SYSTEMS

Using the averaging theory of first and second order we study the maximum number of limit cycles of generalized Linard differential systems{x = y + εh_l~1(x) + ε~2h_l~2(x),y=-x- ε(f_n~1(x)y~(2p+1) + g_m~1(x)) + ∈~2(f_n~2(x)y~(2p+1) + g_m~2(x)),which bifurcate from the periodic orbits of the linear center x = y,y=-x,where ε is a small parameter.The polynomials h_l~1 and h_l~2 have degree l;f_n~1and f_n~2 have degree n;and g_m~1,g_m~2 have degree m.p ∈ N and[·]denotes the integer part function.     

有向圈的笛卡尔积有向图的双控制数

Let γ*(D) denote the twin domination number of digraph D and let Cm Cn denote the Cartesian product of C_m and C_n, the directed cycles of length m, n ≥ 2. In this paper, we determine the exact values: γ*(C_2?C_n) = n; γ*(C_3 ?C_n) = n if n ≡ 0(mod 3),otherwise, γ*(C_3?C_n) = n + 1; γ*(C_4?C_n) = n + n/2 if n ≡ 0, 3, 5(mod 8), otherwise,γ*(C_4?C_n) = n + n/2 + 1; γ*(C_5?C_n) = 2n; γ*(C_6?C_n) = 2n if n ≡ 0(mod 3), otherwise,γ*(C_6?C_n) = 2n + 2.     

Higher-order energy expansions and spike locations

We consider the following singularly perturbed semilinear elliptic problem: where is a bounded domain in R ^N with smooth boundary , is a small constant and f is some superlinear but subcritical nonlinearity. Associated with (I) is the energy functional defined by where . Ni and Takagi ([29, 30]) proved that for a single boundary spike solution , the following asymptotic expansion holds: where c ₁ > 0 is a generic constant, is the unique local maximum point of and is the boundary mean curvature function at . In this paper, we obtain a higher-order expansion of where c ₂, c ₃ are generic constants and is the scalar curvature at . In particular c ₃ > 0. Some applications of this expansion are given.Received: 14 January 2003, Accepted: 28 July 2003, Published online: 15 October 2003Mathematics Subject Classification (2000): Primary 35B40, 35B45; Secondary 35J25     

图的无符号拉普拉斯和距离无符号拉普拉斯特征值

Let G be a simple graph. We first show that ■, where δiand di denote the i-th signless Laplacian eigenvalue and the i-th degree of vertex in G, respectively.Suppose G is a simple and connected graph, then some inequalities on the distance signless Laplacian eigenvalues are obtained by deleting some vertices and some edges from G. In addition, for the distance signless Laplacian spectral radius ρQ(G), we determine the extremal graphs with the minimum ρQ(G) among the trees with given diameter, the unicyclic and bicyclic graphs with given girth, respectively.     

参数函数$\epsilon$取边际值时的$GCF_\epsilon$集

Let ∈ :N → R be a parameter function satisfying the condition ∈(k) + k + 1 > 0and let T∈ :(0,1] →(0,1] be a transformation defined by T∈(x) =-1 +(k + 1)x1 + k-k∈x for x ∈(1k + 1,1k].Under the algorithm T∈,every x ∈(0,1] is attached an expansion,called generalized continued fraction(GCF∈) expansion with parameters by Schweiger.Define the sequence {kn(x)}n≥1of the partial quotients of x by k1(x) = ∈1/x∈ and kn(x) = k1(Tn-1∈(x)) for every n ≥ 2.Under the restriction-k-1 < ∈(k) <-k,define the set of non-recurring GCF∈expansions as F∈= {x ∈(0,1] :kn+1(x) > kn(x) for infinitely many n}.It has been proved by Schweiger that F∈has Lebesgue measure 0.In the present paper,we strengthen this result by showing that{dim H F∈≥12,when ∈(k) =-k-1 + ρ for a constant 0 < ρ < 1;1s+2≤ dimHF∈≤1s,when ∈(k) =-k-1 +1ksfor any s ≥ 1where dim H denotes the Hausdorff dimension.     

New Constructions of Weak ε-Nets

A finite set $N \subset \R^d$ is a {\em weak $\eps$-net} for an $n$-point set $X\subset \R^d$ (with respect to convex sets) if $N$ intersects every convex set $K$ with $|K\,\cap\,X|\geq \eps n$. We give an alternative, and arguably simpler, proof of the fact, first shown by Chazelle et al., that every point set $X$ in $\R^d$ admits a weak $\eps$-net of cardinality $O(\eps^{-d}\polylog(1/\eps))$. Moreover, for a number of special point sets (e.g., for points on the moment curve), our method gives substantially better bounds. The construction yields an algorithm to construct such weak $\eps$-nets in time $O(n\ln(1/\eps))$.     

Krawtchouk多项式的渐近性态

在前人的基础上,对Krawtchouk多项式及其零点的渐近性态进行了研究.首先推导出对于任意固定的u=n/N∈(0,P)或(0,q)Krawtchouk多项式Kn(λN)(其中λ=xN,0<λ<1)的一致有效渐近展开式.然后又得到了它的零点的渐近性态,并对其相应的误差限进行分析.该误差限为o(n-4/3).     

广义Petersen图的宽直径

Generalized Petersen graphs are commonly used interconnection networks,and wide diameter is an important parameter to measure fault-tolerance and efficiency of parallel pro- cessing computer networks.In this paper,we show that the diameter and 3-wide diameter of generalized Petersen graph P (m,a) are both O( m 2a ),where a ≥ 3.     

Testing properties of directed graphs: acyclicity and connectivity*

This article initiates the study of testing properties of directed graphs. In particular, the article considers the most basic property of directed graphs—acyclicity . Because the choice of representation affects the choice of algorithm, the two main representations of graphs are studied. For the adjacency‐matrix representation, most appropriate for dense graphs, a testing algorithm is developed that requires query and time complexity of $\widetilde{O}(1/\epsilon^2)$, where ? is a distance parameter independent of the size of the graph. The algorithm, which can probe the adjacency matrix of the graph, accepts every graph that is acyclic, and rejects, with probability at least 2/3, every graph whose adjacency matrix should be modified in at least ? fraction of its entries so that it becomes acyclic. For the incidence list representation, most appropriate for sparse graphs, an Ω(|V|^1/3) lower bound is proved on the number of queries and the time required for testing, where V is the set of vertices in the graph. Along with acyclicity, this article considers the property of strong connectivity. Contrasting upper and lower bounds are proved for the incidence list representation. In particular, if the testing algorithm can query on both incoming and outgoing edges at each vertex, then it is possible to test strong connectivity in $\widetilde{O}(1/\epsilon)$ time and query complexity. On the other hand, if the testing algorithm only has access to outgoing edges, then $\Omega(\sqrt{N})$ queries are required to test for strong connectivity. © 2002 Wiley Periodicals, Inc. Random Struct. Alg. 20: 184–205, 2002     

图的Augmented Zagreb 指数的界

Let G =(V, E) be a simple connected graph with n(n ≥ 3) vertices and m edges,with vertex degree sequence {d₁, d₂,..., d_n}. The augmented Zagreb index is defined as AZI =AZI(G)=∑ij∈E(didj/di+dj-2)³. Using the properties of inequality, we investigate the bounds of AZI for connected graphs, in particular unicyclic graphs in this paper, some useful conclusions are obtained.