On Some Special Classes of Sequential Dynamical Systems

Sequential Dynamical Systems (SDSs) are mathematical models for analyzing simulation systems. We investigate phase space properties of some special classes of SDSs obtained by restricting the local transition functions used at the nodes. We show that any SDS over the Boolean domain with symmetric Boolean local transition functions can be efficiently simulated by another SDS which uses only simple threshold and simple inverted threshold functions, where the same threshold value is used at each node and the underlying graph is d-regular for some integer d. We establish tight or nearly tight upper and lower bounds on the number of steps needed for SDSs over the Boolean domain with 1-, 2- or 3-threshold functions at each of the nodes to reach a fixed point. When the domain is a unitary semiring and each node computes a linear combination of its inputs, we present a polynomial time algorithm to determine whether such an SDS reaches a fixed point. We also show (through an explicit construction) that there are Boolean SDSs with the NOR function at each node such that their phase spaces contain directed cycles whose length is exponential in the number of nodes of the underlying graph of the SDS.AMS Subject Classification: 68Q10, 68Q17, 68Q80.     

Acyclic edge colorings of graphs

A proper coloring of the edges of a graph G is called acyclic if there is no 2‐colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. For certain graphs G, a′(G) ≥ Δ(G) + 2 where Δ(G) is the maximum degree in G. It is known that a′(G) ≤ 16 Δ(G) for any graph G. We prove that there exists a constant c such that a′(G) ≤ Δ(G) + 2 for any graph G whose girth is at least cΔ(G) log Δ(G), and conjecture that this upper bound for a′(G) holds for all graphs G. We also show that a′(G) ≤ Δ + 2 for almost all Δ‐regular graphs. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 157–167, 2001     

路及其相关图的序列性

设G是一个简单图,在G上当且仅当两个顶点的距离为2时增加一条边,所得的图称为G的平方,记作G2;在G上每个顶点都增加一条悬挂边所得的图称为G的冠,记作I(G).设Pn是n个顶点的路,本文给出了I(Pn2)、I(Fn)、F2n徊和I(Fn2)的序列标号.     

Acyclic List Edge Coloring of Graphs

A proper edge coloring of a graph is said to be acyclic if any cycle is colored with at least three colors. An edge-list L of a graph G is a mapping that assigns a finite set of positive integers to each edge of G. An acyclic edge coloring ? of G such that for any is called an acyclic L-edge coloring of G. A graph G is said to be acyclically k-edge choosable if it has an acyclic L‐edge coloring for any edge‐list L that satisfies for each edge e. The acyclic list chromatic index is the least integer k such that G is acyclically k‐edge choosable. We develop techniques to obtain bounds for the acyclic list chromatic indices of outerplanar graphs, subcubic graphs, and subdivisions of Halin graphs.     

Combinatorics of sequential dynamical systems

In this paper we study sequential dynamical systems (SDS) over words. Our main result is the classification of SDS over words for fixed graph Y and family of local maps (F_vi) by means of a novel notion of SDS equivalence. This equivalence arises from a natural group action on acyclic orientations. An SDS consists of: (a) a graph Y, (b) a family of vertex indexed Y-local maps F_vi:Kⁿ→Kⁿ, where K is a finite field and (c) a word w, i.e. a family (w₁,…,w_k), where w_j is a Y-vertex. A map F_vi(x_v1,…,x_vn) is called Y-local iff it fixes all variables x_vj≠x_vi and depends exclusively on the variables x_vj, for v_j∈B₁(v_i). The SDS-map is obtained by composing the local maps F_vi according to the word w: . Mutual dependencies of the local maps arising from their sequential application are expressed in the graph G(w,Y) having vertex set {1,…,k} (the indices of the word w) and in which r,s are adjacent iff w_s,w_r are adjacent in Y. We prove a bijection from equivalence classes of SDS-words into equivalence classes of acyclic orientations of G(w,Y). We show that within these equivalence classes the induced SDS are equivalent in the sense that their respective phase spaces are isomorphic as digraphs.     

Acyclic 6-choosability of planar graphs without adjacent short cycles

A proper vertex coloring of a graph G is acyclic if G contains no bicolored cycles.Given a list assignment L={L(v)|v∈V}of G,we say that G is acyclically L-colorable if there exists a proper acyclic coloringπof G such thatπ(v)∈L(v)for all v∈V.If G is acyclically L-colorable for any list assignment L with|L(v)|k for all v∈V(G),then G is acyclically k-choosable.In this paper,we prove that every planar graph G is acyclically 6-choosable if G does not contain 4-cycles adjacent to i-cycles for each i∈{3,4,5,6}.This improves the result by Wang and Chen(2009).     

Acyclic edge colorings of planar graphs and seriesparallel graphs

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. Alon et al. conjectured that a′(G) ⩽ Δ(G) + 2 for any graphs. For planar graphs G with girth g(G), we prove that a′(G) ⩽ max{2Δ(G) − 2, Δ(G) + 22} if g(G) ⩾ 3, a′(G) ⩽ Δ(G) + 2 if g(G) ⩾ 5, a′(G) ⩽ Δ(G) + 1 if g(G) ⩾ 7, and a′(G) = Δ(G) if g(G) ⩾ 16 and Δ(G) ⩾ 3. For series-parallel graphs G, we have a′(G) ⩽ Δ(G) + 1. This work was supported by National Natural Science Foundation of China (Grant No. 10871119) and Natural Science Foundation of Shandong Province (Grant No. Y2008A20).     

Acyclic edge chromatic number of outerplanar graphs

A proper edge coloring of a graph G is called acyclic if there is no 2‐colored cycle in G. The acyclic edge chromatic number of G, denoted by χ(G), is the least number of colors in an acyclic edge coloring of G. In this paper, we determine completely the acyclic edge chromatic number of outerplanar graphs. The proof is constructive and supplies a polynomial time algorithm to acyclically color the edges of any outerplanar graph G using χ(G) colors. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 22–36, 2010     

Acyclic 5‐choosability of planar graphs without adjacent short cycles

The conjecture on acyclic 5‐choosability of planar graphs [Borodin et al., 2002] as yet has been verified only for several restricted classes of graphs. None of these classes allows 4‐cycles. We prove that a planar graph is acyclically 5‐choosable if it does not contain an i‐cycle adjacent to a j‐cycle where 3?j?5 if i = 3 and 4?j?6 if i = 4. This result absorbs most of the previous work in this direction. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:169‐176, 2011     

不含相邻三角形的平面图的无圈边着色

An acyclic edge coloring of a graph G is a proper edge coloring such that there are no bichromatic cycles.The acyclic edge chromatic number of a graph G is the minimum number k such that there exists an acyclic edge coloring using k colors and is denoted by χ’ a(G).In this paper we prove that χ ’ a(G) ≤(G) + 5 for planar graphs G without adjacent triangles.     

一类离散动力系统的稳定性

研究一类作 为基因选择模 型的离散动力系 统ｙ ｎ ＋ １ ＝ ｙｎ ｅｂ（ １ － ２ ｙ ｎ － ｋ ）１－ ｙｎ ＋ ｙｎ ｅｂ（ １ － ２ ｙ ｎ － ｋ ） ,　ｎ ＝ ０,１,… ,的稳定性 ,其中 ｂ∈（０,∞）, Ｋ∈ ｛１,２,…｝     

On the Shadowing Property and Shadowable Point of Set-valued Dynamical Systems

In this article, the authors introduce the concept of shadowable points for set-valued dynamical systems, the pointwise version of the shadowing property, and prove that a set-valued dynamical system has the shadowing property iff every point in the phase space is shadowable; every chain transitive set-valued dynamical system has either the shadowing property or no shadowable points; and for a set-valued dynamical system there exists a shadowable point iff there exists a minimal shadowable point. In the end, it is proved that a set-valued dynamical system with the shadowing property is totally transitive iff it is mixing and iff it has the specification property.     

图P_m×C_n和W(m,n)的序列性

给出了图Pm×Cn,I(Pm×Cn)和W(m,n)的序列标号.证明了图Pm×Cn,I(Pm×Cn)和W(m,n)(m≥1,n≥3且n为奇数)是序列图,从而也是调和图.     

Acyclic improper colouring of graphs with maximum degree 4

A k-colouring(not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colours i and j the subgraph induced by the edges whose endpoints have colours i and j is acyclic. We consider acyclic k-colourings such that each colour class induces a graph with a given(hereditary) property. In particular, we consider acyclic k-colourings in which each colour class induces a graph with maximum degree at most t, which are referred to as acyclic t-improper k-colourings. The acyclic t-improper chromatic number of a graph G is the smallest k for which there exists an acyclic t-improper k-colouring of G. We focus on acyclic colourings of graphs with maximum degree 4. We prove that 3 is an upper bound for the acyclic 3-improper chromatic number of this class of graphs. We also provide a non-trivial family of graphs with maximum degree4 whose acyclic 3-improper chromatic number is at most 2, namely, the graphs with maximum average degree at most 3. Finally, we prove that any graph G with Δ(G) 4 can be acyclically coloured with 4 colours in such a way that each colour class induces an acyclic graph with maximum degree at most 3.     

Acyclic edge coloring of planar graphs without adjacent cycles

A proper edge coloring of a graph G is said to be acyclic if there is no bicolored cycle in G.The acyclic edge chromatic number of G,denoted byχ′a(G),is the smallest number of colors in an acyclic edge coloring of G.Let G be a planar graph with maximum degree.In this paper,we show thatχ′a(G)+2,if G has no adjacent i-and j-cycles for any i,j∈{3,4,5},which implies a result of Hou,Liu and Wu(2012);andχ′a(G)+3,if G has no adjacent i-and j-cycles for any i,j∈{3,4,6}.     

On the Stability of Globally Projected Dynamical Systems

Two types of projected dynamical systems, whose equilibrium states solve the corresponding variational inequality problems, were proposed recently by Dupuis and Nagurney (Ref. 1) and by Friesz et al. (Ref. 2). The stability of the dynamical system developed by Dupuis and Nagurney has been studied completely (Ref. 3). This paper analyzes and proves the global asymptotic stability of the dynamical system proposed by Friesz et al. under monotone and symmetric mapping conditions. Furthermore, the dynamical system is shown to be globally exponentially stable under stronger conditions. Finally, we show that the dynamical system proposed by Friesz et al. can be applied easily to neural networks for solving a class of optimization problems.     

On Solvability of Functional Equations Relating to Dynamical Systems with Two Generators

In this paper, some solvability problems for functional equations of the form

Asymptotic Behaviour of the Number of Labelled Essential Acyclic Digraphs and Labelled Chain Graphs

We provide an asymptotic formula for the number of labelled essential DAGs a_n and show that lim_na_n/a_n=c, where a_n is the number of labelled DAGs and c13.65, which is interesting in the field of Bayesian networks. Furthermore, we present an asymptotic formula for the number of labelled chain graphs.Acknowledgment. I would like to thank Prof. Peter Grabner for his support and very helpful discussions, which where constitutive for this article. I am also thankful to the referees for their comments.This Research was supported by the Austrian Science Fund (FWF), START-Project Y96-MATFinal version received: January 28, 2004     

Acyclic edge coloring of triangle-free 1-planar graphs

A proper edge coloring of a graph G is acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by χ a(G), is the least number of colors such that G has an acyclic edge coloring. A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that χ a(G) ≤Δ(G) + 22, if G is a triangle-free 1-planar graph.     

Krylov Subspaces Associated with Higher-Order Linear Dynamical Systems

A standard approach to model reduction of large-scale higher-order linear dynamical systems is to rewrite the system as an equivalent first-order system and then employ Krylov-subspace techniques for model reduction of first-order systems. This paper presents some results about the structure of the block-Krylov subspaces induced by the matrices of such equivalent first-order formulations of higher-order systems. Two general classes of matrices, which exhibit the key structures of the matrices of first-order formulations of higher-order systems, are introduced. It is proved that for both classes, the block-Krylov subspaces induced by the matrices in these classes can be viewed as multiple copies of certain subspaces of the state space of the original higher-order system. AMS subject classification (2000) 65F30, 15A57, 65P99, 41A21