A note on the computational complexity of graph vertex partition

A stable set of a graph is a vertex set in which any two vertices are not adjacent. It was proven in [A. Brandstädt, V.B. Le, T. Szymczak, The complexity of some problems related to graph 3-colorability, Discrete Appl. Math. 89 (1998) 59-73] that the following problem is NP-complete: Given a bipartite graph G, check whether G has a stable set S such thatG-Sis a tree. In this paper we prove the following problem is polynomially solvable: Given a graph G with maximum degree 3 and containing no vertices of degree 2, check whether G has a stable set S such thatG-Sis a tree. Thus we partly answer a question posed by the authors in the above paper. Moreover, we give some structural characterizations for a graph G with maximum degree 3 that has a stable set S such that G-S is a tree.     

确定线性偏微分方程组可积系统的对合特征集方法

基于Ritt-Wu特征集方法和Riquier-Janet理论,给出一种将线性微分方程组化成简单标准形式的有效算法．该算法通过消去冗余和添加可积条件获得线性微分方程组的完全可积系统(有形式幂级数解)或不相容判定．该算法不仅适用于常系数的线性偏微分方程组,而且对于变系数(以函数为系数)仍然有效．作者还给出了完全可积系统判定定理及其严格证明．     

Selection Principles and Sierpinski Sets

We show that a set of real numbers is a Sierpinski set if, and only if, it satisfies a selection property similar to the familiar Menger property.     

A New Family of Cyclic Difference Sets with Singer Parameters in Characteristic Three

We construct a new family of cyclic difference sets with parameters ((3 ^d – 1)/2, (3 ^{d – 1} – 1)/2, (3 ^{d – 2} – 1)/2) for each odd d. The difference sets are constructed with certain maps that form Jacobi sums. These new difference sets are similar to Maschietti's hyperoval difference sets, of the Segre type, in characteristic two. We conclude by calculating the 3-ranks of the new difference sets.     

Isotone relations revisited

We propose a new approach towards proving that the fixed point property for ordered sets is preserved by products. This approach uses a characterization of fixed points in products via isotone relations. First explorations of classes of isotone relations are presented. These first explorations give us hope that this approach could lead to advances on the Product Problem.     

代数课程教学改革的一些探索

本文结合代数教学中的实际情况．针对代数教学过程中出现的问题。提出了在代数教学过程中改进教学方法的几条措施．     

每个算子都是两个强不可约算子的和

本文证明了可分无穷维 Hilbert空间上每个有界线性算子均可写成两个强不可约算子之和 .这回答了文献 [9]中提出一个公开问题     

Choquet-type Integral Representation of Invariant Functions for some Product Semigroups

We show that functions which are invariant for suitable product semigroups (one of which is a quasi-Poisson semigroup on a general state space) decompose into a singular eigen-function and a mixture of products of minimal eigen-functions.     

Second Order Nonlinear Evolution Inclusions Ⅰ： Existence and Relaxation Results

This is the first part of a work on second order nonlinear, nonmonotone evolution inclusions defined in the framework of an evolution triple of spaces and with a multivalued nonlinearity depending on both x（t） and x（t）. In this first part we prove existence and relaxation theorems. We consider the case of an usc, convex valued nonlinearity and we show that for this problem the solution set is nonempty and compact in C^1 （T, H）. Also we examine the Isc, nonconvex case and again we prove the existence of solutions. In addition we establish the existence of extremal solutions and by strengthening our hypotheses, we show that the extremal solutions are dense in C^1 （T, H） to the solutions of the original convex problem （strong relaxation）. An example of a nonlinear hyperbolic optimal control problem is also discussed.     

Positive set‐operators of low complexity

The powerset operator, ??, is compared with other operators of similar type and logical complexity. Namely we examine positive operators whose defining formula has a canonical form containing at most a string of universal quantifiers. We call them ?‐operators. The question we address in this paper is: How is the class of ?‐operators generated ? It is shown that every positive ?‐operator Γ such that Γ(??) ≠ ??, is finitely generated from ??, the identity operator Id, constant operators and certain trivial ones by composition, ∪ and ∩. This extends results of [3] concerning bounded positive operators.