图的导出森林2-划分

对一个给定的简单图Ｇ，是否存在Ｖ（Ｇ）的一个２－划分（Ｖ１，Ｖ２）使得每个导出子图Ｇ［Ｖｉ］为森林？称该问题为导出森林２－划分问题．本文证明了对最大度为５的图该问题是ＮＰ－完全的，而对最大度≤４的图该问题多项式时间可解．     

Two Tree-Width-Like Graph Invariants

In this paper we introduce two tree-width-like graph invariants. The first graph invariant, which we denote by ⁼(G), is defined in terms of positive semi-definite matrices and is similar to the graph invariant (G), introduced by Colin de Verdière in [J. Comb. Theory, Ser. B., 74:121–146, 1998]. The second graph invariant, which we denote by (G), is defined in terms of a certain connected subgraph property and is similar to (G), introduced by van der Holst, Laurent, and Schrijver in [J. Comb. Theory, Ser. B., 65:291–304, 1995]. We give some theorems on the behaviour of these invariants under certain transformations. We show that ⁼(G)=(G) for any graph G with ⁼(G)4, and we give minimal forbidden minor characterizations for the graphs satisfying ⁼(G)k for k=1,2,3,4.This paper is extracted from two chapters of [7]. This work was done while the author was at the Centrum voor Wiskunde en Informatica, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands.     

Badly approximable vectors on fractals

For a large class of closed subsetsC of ℝ ⁿ , we show that the intersection ofC with the set of badly approximable vectors has the same Hausdorff dimension asC. The sets are described in terms of measures they support. Examples include (but are not limited to) self-similar sets such as Cantor’s ternary sets or attractors for irreducible systems of similarities satisfying Hutchinson’s open set condition.     

Two Bounds for the Domination Number of a Graph

Upper and lower bounds are obtained for the domination numberof a graph, by means of a lemma involving the concept of a minimumdominating set of vertices. Although these results are obtainedexplicitly for graphs, there are analogous results in the theoryof directed graphs.     

Badly approximable points on planar curves and a problem of Davenport

Let \({\mathcal {C}}\) be two times continuously differentiable curve in \({\mathbb {R}}^2\) with at least one point at which the curvature is non-zero. For any \(i,j \geqslant 0\) with \(i+j =1\) , let \({\mathbf {Bad}}(i,j)\) denote the set of points \((x,y) \in {\mathbb {R}}^2\) for which \( \max \{ \Vert qx\Vert ^{1/i}, \, \Vert qy\Vert ^{1/j} \} > c/q \) for all \( q \in {\mathbb {N}}\) . Here \(c = c(x,y)\) is a positive constant. Our main result implies that any finite intersection of such sets with \({\mathcal {C}}\) has full Hausdorff dimension. This provides a solution to a problem of Davenport dating back to the sixties.     

Partitioning the Vertices of a Graph into Two Total Dominating Sets

A total dominating set in a graph G is a set S of vertices of G such that every vertex in G is adjacent to a vertex of S. We study graphs whose vertex set can be partitioned into two total dominating sets. In particular, we develop several sufficient conditions for a graph to have a vertex partition into two total dominating sets. We also show that with the exception of the cycle on five vertices, every selfcomplementary graph with minimum degree at least two has such a partition.     

关于乘积图的二维带宽问题

给出一般乘积图的二维带宽的界，并解决一类乘积图的二维带宽问题．最后给出完全ｋ部图的二维带宽。     

基于两种不同延迟过程的退化系统之最优更换策略

将延迟几何过程进行推广并引入延迟α-幂过程,以用于处理退化过程会发生延迟且延迟发生的概率会随故障次数的增多而减小的系统.以系统的故障次数为更换策略,以平均费用率为目标函数,建立了维修更换模型,证明了最优维修更换策略的存在性.最后,通过一个数值例子验证了方法的有效性.     

The Spectrum and Convergence Rates of Exclusion and Interchange Processes on the Complete Graph

We give a short and completely elementary method to find the full spectrum of the exclusion process and a nicely limited superset of the spectrum of the interchange process (a.k.a. random transpositions) on the complete graph. In the case of the exclusion process, this gives a simple closed-form expression for all the eigenvalues and their multiplicities. This result is then used to give an exact expression for the distance in \( L^2 \) from stationarity at any time and upper and lower bounds on the convergence rate for the exclusion process. In the case of the interchange process, upper and lower bounds are similarly found. Our results strengthen or reprove many known results about the mixing time for the two processes in a very simple way.     

两种液体交叉混合的建模问题

对两种液体的交叉离散混合及连续混合进行了讨论,分别建立了两种液体在等量或等速交叉离散混合条件下的递推数列及微分方程模型.     

GARCH过程的同期聚合

我们首先提出由独立一元变量GARCH过程的同期聚合可得到一个弱GARCH过程 (见Drost和Nijman( 1 993) )过程 ,接着分析同期聚合的参数同原始过程参数间的相依性 ,指出聚合后方差参数依赖于原始方差和参数的峰度 .     

Group-invariant Percolation on Graphs

Let G be a closed group of automorphisms of a graph X. We relate geometric properties of G and X, such as amenability and unimodularity, to properties of G-invariant percolation processes on X, such as the number of infinite components, the expected degree, and the topology of the components. Our fundamental tool is a new masstransport technique that has been occasionally used elsewhere and is developed further here.¶ Perhaps surprisingly, these investigations of group-invariant percolation produce results that are new in the Bernoulli setting. Most notably, we prove that critical Bernoulli percolation on any nonamenable Cayley graph has no infinite clusters. More generally, the same is true for any nonamenable graph with a unimodular transitive automorphism group.¶ We show that G is amenable if for all $ \alpha < 1 $ \alpha < 1 , there is a G-invariant site percolation process w \omega on X with $ {\bf P} [x \in \omega] > \alpha $ {\bf P} [x \in \omega] > \alpha for all vertices x and with no infinite components. When G is not amenable, a threshold $ \alpha < 1 $ \alpha < 1 appears. An inequality for the threshold in terms of the isoperimetric constant is obtained, extending an inequality of Häggström for regular trees.¶ If G acts transitively on X, we show that G is unimodular if the expected degree is at least 2 in any G-invariant bond percolation on X with all components infinite.¶ The investigation of dependent percolation also yields some results on automorphism groups of graphs that do not involve percolation.     

Hausdorff Dimension of the Range and the Graph of Stable-Like Processes

We determine the Hausdorff dimension for the range of a class of pure jump Markov processes in \(\mathbb {R}^d\), which turns out to be random and depends on the trajectories of these processes. The key argument is carried out through the SDE representation of these processes. The method developed here also allows to compute the Hausdorff dimension for the graph.     

On the Relation Between Two Minor-Monotone Graph Parameters

, where μ and λ are minor-monotone graph invariants introduced by Colin de Verdière [3] and van der Holst, Laurent, and Schrijver [5]. It is also shown that a graph G exists with . The graphs G with maximal planar complement and , characterised by Kotlov, Lovász, and Vempala, are shown to be forbidden minors for . Received: June 13, 1997     

Algebraic and Badly Approximable Power Series over a Finite Field

We will exhibit certain continued fraction expansions for power series over a finite field, with all the partial quotients of degree one, which are non-quadratic algebraic elements over the field of rational functions.     

The Functional Graph of a Linear Discrete Dynamical System with Two Dominating Vertices

The change of the functional graph of a linear discrete dynamical system is described under transformation of the support graph of the system. Namely, the support graph is transformed by adding two dominating vertices.