Cops and Robbers on Planar‐Directed Graphs

Aigner and Fromme initiated the systematic study of the cop number of a graph by proving the elegant and sharp result that in every connected planar graph, three cops are sufficient to win a natural pursuit game against a single robber. This game, introduced by Nowakowski and Winkler, is commonly known as Cops and Robbers in the combinatorial literature. We extend this study to directed planar graphs, and establish separation from the undirected setting. We exhibit a geometric construction that shows that a sophisticated robber strategy can indefinitely evade three cops on a particular strongly connected planar‐directed graph.     

Powerful digraphs

We introduce the concept of a powerful digraph and establish that a powerful digraph structure is included into the saturated structure of each nonprincipal powerful type p possessing the global pairwise intersection property and the similarity property for the theories of graph structures of type p and some of its first-order definable restrictions (all powerful types in the available theories with finitely many (> 1) pairwise nonisomorphic countable models have this property). We describe the structures of the transitive closures of the saturated powerful digraphs that occur in the models of theories with nonprincipal powerful 1-types provided that the number of nonprincipal 1-types is finite. We prove that a powerful digraph structure, considered in a model of a simple theory, induces an infinite weight, which implies that the powerful digraphs do not occur in the structures of the available classes of the simple theories (like the supersimple or finitely based theories) that do not contain theories with finitely many (> 1) countable models.     

Gaussian integral circulant digraphs

The spectrum of a digraph in general contains real and complex eigenvalues. A digraph is called a Gaussian integral digraph if it has a Gaussian integral spectrum that is all eigenvalues are Gaussian integers. In this paper, we consider Gaussian integral digraphs among circulant digraphs.     

Combinatorics on update digraphs in Boolean networks

Boolean networks have been used as models of gene regulation and other biological networks. One key element in these models is the update schedule, which indicates the order in which states have to be updated. In Aracena et al. (2009) [1], the authors define equivalence classes that relate deterministic update schedules that yield the same update digraph and thus the same dynamical behavior of the network. In this paper we study algorithmical and combinatorial aspects of update digraphs. We show a polynomial characterization of these digraphs, which enables us to characterize the corresponding equivalence classes. We prove that the update digraphs are exactly the projections, on the respective subgraphs, of a complete update digraph with the same number of vertices. Finally, the exact number of complete update digraphs is determined, which provides upper and lower bounds on the number of equivalence classes.     

On the injective envelope of a graded module

Abstract

Let Sing _n be the semigroup of all singular full transformations on the set X _n  = {1, 2,…, n} under the composition of functions. Let E(J _n ? 1) be the set of all idempotents of the top 𝒥-class J _n ? 1 = {α ∈ Sing _n :|im α| = n-1}. For any nonempty subset I of E(J _n  ? 1), the aim of this paper is to find a constructive necessary and sufficient condition for the semiband S(I) = ?I? to be ?-trivial. Further, the semiband S(I) is locally maximal ?-trivial if S(I) is ?-trivial and S(I ∪ {e}) is not ?-trivial for any e ∈ E(J _n ? 1 )\I. As applications, we classify locally maximal ?-trivial subsemibands and locally maximal regular ?-trivial subsemibands of Sing _n , respectively. Moreover, the characterization of which S(I) is a band is obtained.

     

Exponents of a class of two-colored digraphs

A two-colored digraph D is primitive if there exist nonnegative integers h and k with h+k>0 such that for each pair (i, j) of vertices there exists an (h, k)-walk in D from i to j. The exponent of the primitive two-colored digraph D is the minimum value of h+k taken over all such h and k. In this article, we consider special primitive two-colored digraphs whose uncolored digraph has n+s vertices and consist of one n-cycle and one (n???2)-cycle. We give the bounds on the exponents, and the characterizations of the extremal two-colored digraphs.     

Primitive non-powerful sign pattern matrices with base 2

A sign pattern matrix M with zero trace is primitive non-powerful if for some positive integer k, M ^k ?=?J _#. The base l(M) of the primitive non-powerful matrix M is the smallest integer k. By considering the signed digraph S whose adjacent matrix is the primitive non-powerful matrix M, we will show that if l(M)?=?2, the minimum number of non-zero entries of M is 5n???8 or 5n???7 depending on whether n is even or odd.     

Seymour's Second Neighborhood Conjecture for Tournaments Missing a Generalized Star

Seymour's Second Neighborhood Conjecture asserts that every digraph (without digons) has a vertex whose first out‐neighborhood is at most as large as its second out‐neighborhood. We prove its weighted version for tournaments missing a generalized star. As a consequence the weighted version holds for tournaments missing a sun, star, or a complete graph. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:89–94, 2012     

碰撞振动系统中周期轨擦边诱导的混沌激变

基于图胞映射理论, 提出了一种擦边流形的数值逼近方法, 研究了典型Du ng 碰撞振动系统中擦边诱导激变的全局动力学. 研究表明, 周期轨的擦边导致的奇异性使得系统同时产生1 个周期鞍和1 个混沌鞍. 当该周期鞍的稳定流形与不稳定流形发生相切时, 边界激变发生使得该混沌鞍演化为混沌吸引子. 噪声可以诱导周期吸引子发生擦边, 这种擦边导致了1 种内部激变的发生, 表现为该周期吸引子与其吸引盆内部的混沌鞍发生碰撞后演变为1 个混沌吸引子.