On CCE graphs of doubly partial orders

Let D be a digraph. The competition-common enemy graph (CCE graph) of D has the same set of vertices as D and an edge between vertices u and v if and only if there are vertices w and x in D such that (w,u), (w,v), (u,x), and (v,x) are arcs of D. We call a graph a CCE graph if it is the CCE graph of some digraph. In this paper, we show that if the CCE graph of a doubly partial order does not contain C₄ as an induced subgraph, it is an interval graph. We also show that any interval graph together with enough isolated vertices is the CCE graph of some doubly partial order.     

Energy minimization and design for testability

The problem of fault detection in general combinational circuits is NP-complete. The only previous result on identifying easily testable circuits is due to Fujiwara who gave a polynomial time algorithm for detecting any single stuck fault inK-bounded circuits. Such circuits may only contain logic blocks with no more thanK input lines and the blocks are so connected that there is no reconvergent fanout among them. We introduce a new class of combinational circuits called the (k, K)-circuits and present a polynomial time algorithm to detect any single or multiple stuck fault in such circuits. We represent the circuit as an undirected graphG with a vertex for each gate and an edge between a pair of vertices whenever the corresponding gates have a connection. For a (k, K)-circuit,G is a subgraph of ak-tree, which, by definition, cannot have a clique of size greater thank+1. Basically, this is a restriction on gate interconnections rather than on the function of gates comprising the circuit. The (k, K)-circuits are a generalization of Fujiwara'sK-bounded circuits. Using the bidirectional neural network model of the circuit and the energy function minimization formulation of the fault detection problem, we present a test generation algorithm for single and multiple faults in (k, K)-circuits. This polynomial time aggorithm minimizes the energy function by recursively eliminating the variables.     

Thermal stability of poly(mono-n-alkylitaconates) and mono-n-alkylitaconate-co-vinylpyrrolidone copolymers I

Poly(monoitaconates) containing octyl, decyl and dodecyl groups and random monoalkylitaconate-co-vinylpyrrolidone copolymers were studied by thermogravimetric analysis. Copolymers of mono-n-octylitaconate (MOI), mono-n-decylitaconate (MDI), and mono-n-dodecylitaconate (MDoI), respectively, with N-vinyl-2-pyrrolidone (VP) of different compositions were studied by dynamic thermogravimetric analysis. The thermal stability of the copolymers depends on the structure of the monoitaconate comonomer and on the composition of the copolymer The kinetic analysis of the degradation data shows that the thermal decomposition of these copolymers can be described by several kinetic orders depending on the copolymer and on the composition. The relative thermal stability of the copolymers increases as the VP content increases and as the length of the side chain of the itaconate increases, following the same trend as the flexibility of the copolymers in solution.     

RECURSIVE BAIRE CLASSIFICATION AND SPEEDABLE FUNCTIONS

Using recursive variants of Baire notions of nowhere dense and meagre sets we study the topological size of speedable and infinitely often speedable functions in a machine-independent framework. We show that the set of speedable functions is not “small” whereas the set of infinitely often speedable functions is “large”. In this way we offer partial answers to a question in [4].     

LA RECONSTRUCTION DES TOURNOIS SANS DIAMANT

We prove that if T is a tournament of order n > 6 in which any 4-sub-tournament is hamiltonian or transitive, then T is reconstructible in the sense of Ulam.     

Linear Ramsey numbers of sparse graphs

The Ramsey number R(G₁,G₂) of two graphs G₁ and G₂ is the least integer p so that either a graph G of order p contains a copy of G₁ or its complement G^c contains a copy of G₂. In 1973, Burr and Erd?s offered a total of $25 for settling the conjecture that there is a constant c = c(d) so that R(G,G)≤ c|V(G)| for all d‐degenerate graphs G, i.e., the Ramsey numbers grow linearly for d‐degenerate graphs. We show in this paper that the Ramsey numbers grow linearly for degenerate graphs versus some sparser graphs, arrangeable graphs, and crowns for example. This implies that the Ramsey numbers grow linearly for degenerate graphs versus graphs with bounded maximum degree, planar graphs, or graphs without containing any topological minor of a fixed clique, etc. © 2005 Wiley Periodicals, Inc. J Graph Theory     

完全二部图Ka,b的迭线图L^m（Ka，b）的谱特征

本证明了当(a，b)不属于{(1，8)，(2，4)，(3，6)，(4，4)，(2s^2-s，2s^2 s))时，L^m(Ka,b)以谱为特征，其中a≤b，s≥2．     

(a,b,n)-临界图的几个充分条件

设G是一个图 .设g和f是两个定义在V(G)上的整值函数使得对V(G)所有顶点x有g(x) ≤f(x) .图G被称为 (g ,f,n) 临界图 ,如果删去G的任意n个顶点后的子图都含有G的 (g ,f) 因子 .本文给出了图是 (a ,b ,n) 临界图几个充分条件 ,即度和邻域条件 .进一步指出这些条件是最佳的 .     

About the Notion of Semiring of Sets

We introduce a generalized notion of semiring and prove that all known properties that semirings have according to the old definition are preserved.     

Dynamics of Random One-Dimensional ±J Systems

Finite chains of a two-state random Potts spin model with periodic boundary conditions are studied within Glauber dynamics. The spin exchange is assumed random with frustration between ferro and antiferromagnetic values (±J). Time-dependent fluctuations are induced by periodic temperature oscillations. Master type differential equations for spin correlation functions are solved within linear response theory. The spectrum of relaxation times are calculated at different temperatures. The ±J Potts glass chains undergo a zero temperature phase transition. The barriers against inversion of the spin chain take only two values; 0 and 2|J|. The temperature behaviour of specific heat is characterized by rounded peaks. The frequency dependence displays two plateaus for the real part of specific heat and two corresponding peaks for the imaginary part. The dynamic specific heat is not affected by the longest relaxing mode like susceptibility. The time separation of the modes is demonstrated by the Cole-Cole plots.