传递子集的性质及其在符号动力系统中的应用

讨论了传递子集的一些性质,并且应用这些性质研究符号动力系统的弱混合子集和传递子集之间的关系,给出了符号动力系统的传递子集是弱混合子集的一个充分条件.     

Alth?fer-Sillke不等式的改进（英）

在本文中给出二元向量空间的子集的平均Hamming距离的一个新的下界和上界，这些界对于二元向量空间的线性子空间是紧的，且改进了[2]文的Alth?fer- Sillke不等式，从而部分解决了Ahlswede和Katona在[1]中提出的一个问题.     

最小最大树划分的近似算法与最小和树划分的精确算法

本文研究把连通赋权图的点集划分成p个子集,要求每个点子集的导出子图都连通,并且使得所得到的p个子图的最小支撑树中权重最大者的权重达到最小(最小最大树划分问题),或者使得所得到的p个子图的最小支撑树权重之和达到最小(最小和树划分问题)．文中给出了最小最大树划分问题的强NP困难性证明,并给出了一个多项式时间算法,该算法是最小最大树划分问题的竞争比为p的近似算法,同时是最小和树划分问题的精确算法．     

子集的交叉t－相交定理

设Ｘ为一个ｎ元集合，Ｃｎｋ为Ｘ的所有ｋ元子集全体，若Ａ∈Ａ，Ｂ∈Ｂ有｜Ａ∩Ｂ｜≥ｔ，则称（Ａ，Ｂ）为一个交叉ｔ－相交子集族．本文得到最大交叉ｔ－相交子集族和最大非空交叉２－相交子集族．证明如下两个结论．（１）若（Ａ，Ｂ）为一个交叉ｔ－相交子集族，且ａ≤ｂ及ａ＋ｂ≤ｎ＋ｔ－１，则｜Ａ＋Ｂ｜≤ｍａｘ｛（ｂｎ），（ａｎ）｝，且当（Ａ；Ｂ）＝（φ，Ｃｎｂ）或（Ｃｎａ，φ）时达到上界．（２）若（Ａ，Ｂ）为一个交叉２－相交子集族，且ａ＜ｂ，ａ＋ｂ≤ｎ－１及（ｎ，ａ，ｂ）≠（２ｉ，ｉ－１，ｉ）（ｉ为任意正整数），又Ａ，Ｂ均非空，则｜Ａ＋Ｂ｜≤１＋（ｂｎ）－（ｂ（ｎ－ａ））－ａ（（ｂ－１）（ｎ－ａ））且当（Ａ，Ｂ）＝（｛Ａ｝，Ｃｎｂ－｛Ｂ｜｜Ｂ｜＝ｂ，｜Ａ∩Ｂ｜≤１｝）时达到上界．     

微分方程零解的弱渐近稳定与不稳定的判定定理

给出了平凡解弱渐近稳定定义及在已知导函数 d Vdt负定的情况下 ,通过 V( t,x)函数的符号性质来判定微分方程平凡解的弱渐近稳定性与不稳定性 ,并举例说明定理的应用 .     

峰严格递增的Dyck路的计数

本文考虑了由最高峰的高度为m,并且峰的高度沿着Dyck路严格递增的所有Dyck路组成的集合,即集合Dm的子集的计数问题．利用双射、生成树以及Riordan阵的方法来对集合Dm的一些子集进行计数,得到了一些以经典的序列如Catalan数、Narayana数、Motzkin数、Fibonacci数、Schroder数以及第一类无符号Stirling数来计数的组合结构．特别地,我们给出了两个新的Catalan结构,它们并没有明显地出现在Stanley关于Catalan结构的列表中．     

匹配数确定的树的序集

源于理论化学，对顶点数相同的树据其匹配的大小可为树定义一个凝序．文献[1]～[8]研究了这一凝序．本文进一步给出此凝序下的四个全序子集．不同于以前的研究，本文讨论的是边较为密集的情形，而以前确定的序集多属二度顶点数较多的情形．     

关于贴近度的定义

本文在［１］的基础上，指出了［１］中的Ｆｕｚｚｙ子集贴近度定义的不完善之处，并给出了另一较完善的Ｆｕｚｚｙ子集贴近度的定义和性质．     

给定阶与边独立数的树和单圈图的Laplacian矩阵的最大特征值

得到了给定顶点数和边独立数的树与单圈图的Laplacian矩阵的最大特征值的精确上界，并且给出了达到上界的所有极图．     

关于图的符号边全控制数

引入了图的符号边全控制的概念,给出了一个连通图G的符号边全控制数γs′t(G)的下限,确定所有n阶树T的最小符号边全控制数,并刻划了满足γs′t(G)=E(G)的所有连通图G,最后还提出了一个关于γs′t(G)上界的猜想.     

On Maximal Inequalities for Stable Stochastic Integrals

Sharp maximal inequalities in large and small range are derived for stable stochastic integrals. In order to control the tail of a stable process, we introduce a truncation level in the support of its Lévy measure: we show that the contribution of the compound Poisson stochastic integral is negligible as the truncation level is large, so that the study is reduced to establish maximal inequalities for the martingale part with a suitable choice of truncation level. The main problem addressed in this paper is to give upper bounds which remain bounded as the parameter of stability of the underlying stable process goes to 2. Applications to estimates of first passage times of symmetric stable processes above positive continuous curves complete this work.      

Maximizing the number of independent subsets over trees with bounded degree

The number of independent vertex subsets is a graph parameter that is, apart from its purely mathematical importance, of interest in mathematical chemistry. In particular, the problem of maximizing or minimizing the number of independent vertex subsets within a given class of graphs has already been investigated by many authors. In view of the applications of this graph parameter, trees of restricted degree are of particular interest. In the current article, we give a characterization of the trees with given maximum degree which maximize the number of independent subsets, and show that these trees also minimize the number of independent edge subsets. The structure of these trees is quite interesting and unexpected: it can be described by means of a novel digital system—in the case of maximum degree 3, we obtain a binary system using the digits 1 and 4. The proof mainly depends on an exchange lemma for branches of a tree. © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 49–68, 2008     

On routing in VLSI design and communication networks

In this paper, we study the global routing problem in VLSI design and the multicast routing problem in communication networks. First we propose new and realistic models for both problems. In the global routing problem in VLSI design, we are given a lattice graph and subsets of the vertex set. The goal is to generate trees spanning these vertices in the subsets to minimize a linear combination of overall wirelength (edge length) and the number of bends of trees with respect to edge capacity constraints. In the multicast routing problem in communication networks, a graph is given to represent the network, together with subsets of the vertex set. We are required to find trees to span the given subsets and the overall edge length is minimized with respect to capacity constraints. Both problems are APX-hard. We present the integer linear programming (LP) formulation of both problems and solve the LP relaxations by the fast approximation algorithms for min-max resource-sharing problems in [K. Jansen, H. Zhang, Approximation algorithms for general packing problems and their application to the multicast congestion problem, Math. Programming, to appear, doi:10.1007/s10107-007-0106-8] (which is a generalization of the approximation algorithm proposed by Grigoriadis and Khachiyan [Coordination complexity of parallel price-directive decomposition, Math. Oper. Res. 2 (1996) 321-340]). For the global routing problem, we investigate the particular property of lattice graphs and propose a combinatorial technique to overcome the hardness due to the bend-dependent vertex cost. Finally, we develop asymptotic approximation algorithms for both problems with ratios depending on the best known approximation ratio for the minimum Steiner tree problem. They are the first known theoretical approximation bound results for the problems of minimizing the total costs (including both the edge and the bend costs) while spanning all given subsets of vertices.     

Symbolic powers of monomial ideals and vertex cover algebras

We introduce and study vertex cover algebras of weighted simplicial complexes. These algebras are special classes of symbolic Rees algebras. We show that symbolic Rees algebras of monomial ideals are finitely generated and that such an algebra is normal and Cohen-Macaulay if the monomial ideal is squarefree. For a simple graph, the vertex cover algebra is generated by elements of degree 2, and it is standard graded if and only if the graph is bipartite. We also give a general upper bound for the maximal degree of the generators of vertex cover algebras.     

Total domination stable graphs upon edge addition

A set S of vertices in a graph G is a total dominating set if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number of G. A graph is total domination edge addition stable if the addition of an arbitrary edge has no effect on the total domination number. In this paper, we characterize total domination edge addition stable graphs. We determine a sharp upper bound on the total domination number of total domination edge addition stable graphs, and we determine which combinations of order and total domination number are attainable. We finish this work with an investigation of claw-free total domination edge addition stable graphs.     

A quadratic programming approach to the determination of an upper bound on the weighted stability number

In a previous work, the authors have introduced an upper bound on the stability number of a graph and several of its properties were given. The determination of this upper bound was done by a quadratic programming approach whose implementation has given good computational results. We now extend this bound to the weighted case, i.e., an upper bound on the weighted stability of an arbitrary graph with node weights is presented. Similarly to the non-weighted case, the deduced bound allows us to give a necessary and sufficient condition to a weighted graph that attains the given bound. Also a heuristic for determining the maximum weight stable set is proposed which is based on an integrality property of a convex quadratic problem that produces the bound. Some comments about the proposed approach will conclude the paper.     

线性不确定系统的稳定控制鲁棒界和多级稳定鲁棒控制

利用李雅普诺夫稳定性理论研究了线性不确定系统的稳定鲁棒控制问题,得到结果“任何一个稳定控制都是具有一定稳定鲁棒界的稳定控制”.进一步地,根据系统的不确定量的范围,设计了多级稳定鲁棒控制策略.最后给出一个例子说明设计步骤的可行性.     

Du Fort-Frankel格式及DFF-I并行格式的稳定性

 本文对抛物型方程的Du Fort-Frankel(DFF)格式以及基于该格式构造的并行差分格式(DFF-I)进行了稳定性分析。采用矩阵分析方法, 证明了其无条件(LR)稳定性, 给出了DFF格式的稳定性系数的最小值的上界估计, 结果表明其与网格比有关, 从而DFF格式并非绝对稳定。本文改进了并行差分格式(DFF-I)的稳定性分析结果, 证明了其增长矩阵的谱半径严格小于1, 从而具有长时间稳定性。数值算例验证了DFF-I格式具有空间二阶精度, 且有很好的稳定性。     

Coefficients of ergodicity and the scrambling index

For a primitive stochastic matrix S, upper bounds on the second largest modulus of an eigenvalue of S are very important, because they determine the asymptotic rate of convergence of the sequence of powers of the corresponding matrix. In this paper, we introduce the definition of the scrambling index for a primitive digraph. The scrambling index of a primitive digraph D is the smallest positive integer k such that for every pair of vertices u and v, there is a vertex w such that we can get to w from u and v in D by directed walks of length k; it is denoted by k(D). We investigate the scrambling index for primitive digraphs, and give an upper bound on the scrambling index of a primitive digraph in terms of the order and the girth of the digraph. By doing so we provide an attainable upper bound on the second largest modulus of eigenvalues of a primitive matrix that make use of the scrambling index.     

Bounds on the Rubbling and Optimal Rubbling Numbers of Graphs

A pebbling move on a graph removes two pebbles at a vertex and adds one pebble at an adjacent vertex. Rubbling is a version of pebbling where an additional move is allowed. In this new move, one pebble each is removed at vertices v and w adjacent to a vertex u, and an extra pebble is added at vertex u. A vertex is reachable from a pebble distribution if it is possible to move a pebble to that vertex using rubbling moves. The rubbling number is the smallest number m needed to guarantee that any vertex is reachable from any pebble distribution of m pebbles. The optimal rubbling number is the smallest number m needed to guarantee a pebble distribution of m pebbles from which any vertex is reachable. We give bounds for rubbling and optimal rubbling numbers. In particular, we find an upper bound for the rubbling number of n-vertex, diameter d graphs, and estimates for the maximum rubbling number of diameter 2 graphs. We also give a sharp upper bound for the optimal rubbling number, and sharp upper and lower bounds in terms of the diameter.