Asynchronous threshold networks

LetG=(V,E) be a graph with an initial signs(v)∈{±1} for every vertexv∈V. When a certexv becomesactive, it resets its sign tos′(v) which is the sign of the majority of its neighbors(s′(v)=1 if there is a tie).G is in astable state if,s′(v) for allv∈V. We show that for every graphG=(V,E) and every initial signs, there is a sequencev ₁,v ₂,...,v _r of vertices ofG, in which no vertex appears more than once, such that ifv _i becomes active at timei, (1≤i≤r), then after theser stepsG reaches a stable state. This proves a conjecture of Miller. We also consider some generalizations to directed graphs with weighted edges.     

Degree sequences of graphs containing a cycle with prescribed length

Let r ≥ 3, n ≥ r and π = (d ₁, d ₂, ..., d _n ) be a non-increasing sequence of nonnegative integers. If π has a realization G with vertex set V (G) = {v ₁, v ₂, ..., v _n } such that d _G (v _i ) = d _i for i = 1, 2, ..., n and v ₁ v ₂ ... v _r v ₁ is a cycle of length r in G, then π is said to be potentially C _r ″-graphic. In this paper, we give a characterization for π to be potentially C _r ″-graphic. This work was supported by the grant of National Natural Science Foundation of China No. 10861006 and China Scholarship Council.     

Distance and fractional isomorphism in Steiner triple systems

In [8], Quattrochi and Rinaldi introduced the idea ofn ⁻¹-isomorphism between Steiner systems. In this paper we study this concept in the context of Steiner triple systems. The main result is that for any positive integerN, there existsv ₀(N) such that for all admissiblev≥v ₀(N) and for each STS(v) (sayS), there exists an STS(v) (sayS′) such that for somen>N, S is strictlyn ⁻¹-isomorphic toS′. We also prove that for all admissiblev≥13, there exist two STS(v)s which are strictly 2⁻¹-isomorphic. Define the distance between two Steiner triple systemsS andS′ of the same order to be the minimum volume of a tradeT which transformsS into a system isomorphic toS′. We determine the distance between any two Steiner triple systems of order 15 and, further, give a complete classification of strictly 2⁻¹-isomorphic and 3⁻¹-isomorphic pairs of STS(15)s.     

1‐Rotational Steiner triple systems over arbitrary groups

Phelps and Rosa introduced the concept of 1‐rotational Steiner triple system, that is an STS(ν) admitting an automorphism consisting of a fixed point and a single cycle of length ν ? 1 [Discrete Math. 33 ( 12 ), 57–66]. They proved that such an STS(ν) exists if and only if ν ≡ 3 or 9 (mod 24). Here, we speak of a 1‐rotational STS(ν) in a more general sense. An STS(ν) is 1‐rotational over a group G when it admits G as an automorphism group, fixing one point and acting regularly on the other points. Thus the STS(ν)'s by Phelps and Rosa are 1‐rotational over the cyclic group. We denote by ??_1r, ??_1r, ??_1r, ??_1r, the spectrum of values of ν for which there exists a 1‐rotational STS(ν) over an abelian, a cyclic, a dicyclic, and an arbitrary group, respectively. In this paper, we determine ??_1r and find partial answers about ??_1r and ??_1r. The smallest 1‐rotational STSs have orders 9, 19, 25 and are unique up to isomorphism. In particular, the only 1‐rotational STS(25) is over SL₂(3), the special linear group of dimension 2 over Z₃. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 215–226, 2001     

A new existence proof for large sets of disjoint Steiner triple systems

A Steiner triple system of order v (briefly STS(v)) consists of a v-element set X and a collection of 3-element subsets of X, called blocks, such that every pair of distinct points in X is contained in a unique block. A large set of disjoint STS(v) (briefly LSTS(v)) is a partition of all 3-subsets (triples) of X into v-2 STS(v). In 1983–1984, Lu Jiaxi first proved that there exists an LSTS(v) for any v≡1 or with six possible exceptions and a definite exception v=7. In 1989, Teirlinck solved the existence of LSTS(v) for the remaining six orders. Since their proof is very complicated, it is much desired to find a simple proof. For this purpose, we give a new proof which is mainly based on the 3-wise balanced designs and partitionable candelabra systems.     

Large Sets and Overlarge Sets of Triangle-Decomposition

There are six types of triangles:undirected triangle,cyclic triangle,transitive triangle,mixed-1triangle,mixed-2 triangle and mixed-3 triangle.The triangle-decompositions for the six types of triangles havealready been solved.For the first three types of triangles,their large sets have already been solved,and theiroverlarge sets have been investigated.In this paper,we establish the spectrum of LT_i(v,λ),OLT_i(v)(i=1,2),and give the existence of LT_3(v,λ)and OLT_3(v,λ)with λ even.     

Degree series of the 3-harmonic graphs

A λ harmonic graph G, a λ-Hgraph G for short, means that there exists a constant λ such that the equality λd（vi） = Σ（vi,vj）∈E（G） d（vj） holds for all i = 1, 2,..., ｜V（G）｜, where d（vi） denotes the degree of vertex vi. Let ni denote the number of vertices with degree i. This paper deals with the 3-Hgraphs and determines their degree series. Moreover, the 3-Hgraphs with bounded ni （1 ≤ i ≤ 7） are studied and some interesting results are obtained.     

Diperfect graphs

Gallai and Milgram have shown that the vertices of a directed graph, with stability number α(G), can be covered by exactly α(G) disjoint paths. However, the various proofs of this result do not imply the existence of a maximum stable setS and of a partition of the vertex-set into paths μ₁, μ₂, ..., μ_k such tht |μ_i ∩S|=1 for alli. Later, Gallai proved that in a directed graph, the maximum number of vertices in a path is at least equal to the chromatic number; here again, we do not know if there exists an optimal coloring (S ₁,S ₂, ...,S _k) and a path μ such that |μ ∩S _i|=1 for alli. In this paper we show that many directed graphs, like the perfect graphs, have stronger properties: for every maximal stable setS there exists a partition of the vertex set into paths which meet the stable set in only one point. Also: for every optimal coloring there exists a path which meets each color class in only one point. This suggests several conjecties similar to the perfect graph conjecture. Dedicated to Tibor Gallai on his seventieth birthday     

Partition conditions and vertex-connectivity of graphs

It was proved ([5], [6]) that ifG is ann-vertex-connected graph then for any vertex sequencev ₁, ...,v _n ≠V(G) and for any sequence of positive integersk ₁, ...,k _n such thatk ₁+...+k _n =|V(G)|, there exists ann-partition ofV(G) such that this partition separates the verticesv ₁, ...,v(n), and the class of the partition containingv _i induces a connected subgraph consisting ofk _i vertices, fori=1, 2, ...,n. Now fix the integersk ₁, ...,k _n . In this paper we study what can we say about the vertex-connectivity ofG if there exists such a partition ofV(G) for any sequence of verticesv ₁, ...,v _n ≠V(G). We find some interesting cases when the existence of such partitions implies then-vertex-connectivity ofG, in the other cases we give sharp lower bounds for the vertex-connectivity ofG.     

Chaos caused by a strong-mixing measure-preserving transformation

The chaos caused by a strong-mixing preserving transformation is discussed and it is shown that for a topological spaceX satisfying the second axiom of countability and for an outer measurem onX satisfying the conditions: (i) every non-empty open set ofX ism-measurable with positivem-measure; (ii) the restriction ofm on Borel σ-algebra ℬ(X) ofX is a probability measure, and (iii) for everyY⊂X there exists a Borel setB⊂ℬ(X) such thatB⊃Y andm(B) =m(Y), iff:X→X is a strong-mixing measure-preserving transformation of the probability space (X, ℬ(X),m), and if {m}, is a strictly increasing sequence of positive integers, then there exists a subsetC⊂X withm (C) = 1, finitely chaotic with respect to the sequence {m _i}, i.e. for any finite subsetA ofC and for any mapF:A→X there is a subsequencer _i such that lim_i→∞ f ^r i(a) =F(a) for anya ∈A. There are some applications to maps of one dimension. the National Natural Science Foundation of China.     

Another construction for large sets of Kirkman triple systems

A large set of Kirkman triple systems of order v, denoted by LKTS(v), is a collection , where every is a KTS(v) and all form a partition of all triples on X. In this article, we give a new construction for LKTS(6v + 3) via OLKTS(2v + 1) with a special property and obtain new results for LKTS, that is there exists an LKTS(3v) for , where p, q ≥ 0, r _i , s _j ≥ 1, q _i is a prime power and mod 12.      

Further 6-sparse Steiner Triple Systems

We give a construction that produces 6-sparse Steiner triple systems of order v for all sufficiently large v of the form 3p, p prime and p ≡ 3 (mod 4). We also give a complete list of all 429 6-sparse systems with v < 10000 produced by this construction.     

On λ-harmonic graphs

A λ harmonic graph G, a λ-Hgraph G for short, means that there exists a constant A such that the equality λd（ui） = ∑（vi,vj）∈E（G） d（vj） holds for all i = 1, 2,…, ｜V（G）｜, where d（vi） denotes the degree of vertex vi. In this paper, some harmonic properties of the complement and line graph are given, and some algebraic properties for the λ-Hgraphs are obtained.     

A remark on degree sequences of multigraphs

A sequence {d ₁, d ₂, . . . , d _n } of nonnegative integers is graphic (multigraphic) if there exists a simple graph (multigraph) with vertices v ₁, v ₂, . . . , v _n such that the degree d(v _i ) of the vertex v _i equals d _i for each i = 1, 2, . . . , n. The (multi) graphic degree sequence problem is: Given a sequence of nonnegative integers, determine whether it is (multi)graphic or not. In this paper we characterize sequences that are multigraphic in a similar way, Havel (Časopis Pěst Mat 80:477–480, 1955) and Hakimi (J Soc Indust Appl Math 10:496–506, 1962) characterized graphic sequences. Results of Hakimi (J Soc Indust Appl Math 10:496–506, 1962) and Butler, Boesch and Harary (IEEE Trans Circuits Syst CAS-23(12):778–782, 1976) follow.     

Stability of <Emphasis Type="Italic">C</Emphasis>-regularized Semigroups

Let T = (T(t))t≥0 be a bounded C-regularized semigroup generated by A on a Banach space X and R(C) be dense in X. We show that if there is a dense subspace Y of X such that for every x ∈ Y, σu(A, Cx), the set of all points λ ∈ iR to which (λ - A)^-1 Cx can not be extended holomorphically, is at most countable and σr(A) N iR = Ф, then T is stable. A stability result for the case of R(C) being non-dense is also given. Our results generalize the work on the stability of strongly continuous senfigroups.     

A Geometric Proof of the Colored Tverberg Theorem

The colored Tverberg theorem asserts that for every d and r there exists t=t(d,r) such that for every set C⊂ℝ ^d of cardinality (d+1)t, partitioned into t-point subsets C ₁,C ₂,…,C _d+1 (which we think of as color classes; e.g., the points of C ₁ are red, the points of C ₂ blue, etc.), there exist r disjoint sets R ₁,R ₂,…,R _r ⊆C that are rainbow, meaning that |R _i ∩C _j |≤1 for every i,j, and whose convex hulls all have a common point.     

On automorphisms of some finite <Emphasis Type="Italic">p</Emphasis>-groups

We give a sufficient condition on a finite p-group G of nilpotency class 2 so that Aut _c (G) = Inn(G), where Aut _c (G) and Inn(G) denote the group of all class preserving automorphisms and inner automorphisms of G respectively. Next we prove that if G and H are two isoclinic finite groups (in the sense of P. Hall), then Aut _c (G) ≃ Aut _c (H). Finally we study class preserving automorphisms of groups of order p ⁵, p an odd prime and prove that Aut _c (G) = Inn(G) for all the groups G of order p ⁵ except two isoclinism families.     

Constructions for large sets of <Emphasis Type="Italic">L</Emphasis>-intersecting Steiner triple systems

Recently, Franek et al. introduced large sets of v − 1 L-intersecting Steiner triple systems of order v (STS(v)) and gave four constructions for them (Des., Codes and Cryptogr., 26 (2002), 243–256). In this paper, we mainly focus on large sets of v − 1{0, 1}-intersecting STS(v) and large sets of v + 1{1}-intersecting STS(v). For this purpose, we introduce a concept of L-intersecting partitionable candelabra system (L-PCS) of order v with q(v) subsystems and establish a relationship between L-PCS and large set of q(v)L-intersecting STS(v). Some constructions for L-PCSs are also presented by 3-wise balanced designs. These facilitate the production of some new infinite classes of these large sets. Research supported by Tianyuan Mathematics Foundation of NSFC Grant 10526032 and Natural Science Foundation of Universities of Jiangsu Province Grant 05KJB110111.     

Two Paths Joining Given Vertices in 2k-Edge-Connected Graphs

Let k≥2 be an integer and G = (V(G), E(G)) be a k-edge-connected graph. For X⊆V(G), e(X) denotes the number of edges between X and V(G) − X. Let {s_i, t_i}⊆X_i⊆V(G) (i=1,2) and X₁∩X₂=∅. We here prove that if k is even and e(X_i)≤2k−1 (i=1,2), then there exist paths P₁ and P₂ such that P_i joins s_i and t_i, V(P_i)⊆X_i (i=1,2) and G − E(P₁∪P₂) is (k−2)-edge-connected (for odd k, if e(X₁)≤2k−2 and e(X₂)≤2k−1, then the same result holds [10]), and we give a generalization of this result and some other results about paths not containing given edges.     

On Cycle Sequences

. For each vertex v in a graph G, the maximum length of a cycle which passes through v is called the cycle number of v, denoted by c(v). A sequence a ₁,a ₂,…,a _n of nonnegative integers is called a cycle sequence of a graph G if the vertices of G can be labeled as v ₁,v ₂,…,v _n such that a _i =c(v _i ) for 1≤i≤n. We give some sufficient and necessary conditions for a sequence to be a cycle sequence. We can thereby derive a polynomial time procedure for recognizing cycle sequences. Received: July 14, 1997 Final version received: June 15, 1998