A Survey of Reachability and Controllability for Positive Linear Systems

This paper is a survey of reachability and controllability results for discrete-time positive linear systems. It presents a variety of criteria in both algebraic and digraph forms for recognising these fundamental system properties with direct implications not only in dynamic optimization problems (such as those arising in inventory and production control, manpower planning, scheduling and other areas of operations research) but also in studying properties of reachable sets, in feedback control problems, and others. The paper highlights the intrinsic combinatorial structure of reachable/controllable positive linear systems and reveals the monomial components of such systems. The system matrix decomposition into monomial components is demonstrated by solving some illustrative examples.     

The Second Neighbourhood for Quasi-transitive Oriented Graphs

In 2006, Sullivan stated the conjectures:(1) every oriented graph has a vertex x such that d~(++)(x) ≥ d~-(x);(2) every oriented graph has a vertex x such that d~(++)(x) + d~+(x) ≥ 2 d~-(x);(3) every oriented graph has a vertex x such that d~(++)(x) + d~+(x) ≥ 2 · min{d~+(x), d~-(x)}. A vertex x in D satisfying Conjecture(i) is called a Sullivan-i vertex, i = 1, 2, 3. A digraph D is called quasi-transitive if for every pair xy, yz of arcs between distinct vertices x, y, z, xz or zx("or" is inclusive here) is in D. In this paper, we prove that the conjectures hold for quasi-transitive oriented graphs, which is a superclass of tournaments and transitive acyclic digraphs. Furthermore, we show that a quasi-transitive oriented graph with no vertex of in-degree zero has at least three Sullivan-1 vertices and a quasi-transitive oriented graph has at least three Sullivan-3 vertices unless it belongs to an exceptional class of quasitransitive oriented graphs. For Sullivan-2 vertices, we show that an extended tournament, a subclass of quasi-transitive oriented graphs and a superclass of tournaments, has at least two Sullivan-2 vertices unless it belongs to an exceptional class of extended tournaments.     

On the structure of strong 3-quasi-transitive digraphs

In this paper, D=(V(D),A(D)) denotes a loopless directed graph (digraph) with at most one arc from u to v for every pair of vertices u and v of V(D). Given a digraph D, we say that D is 3-quasi-transitive if, whenever u→v→w→z in D, then u and z are adjacent or u=z. In Bang-Jensen (2004) [3], Bang-Jensen introduced 3-quasi-transitive digraphs and claimed that the only strong 3-quasi-transitive digraphs are the strong semicomplete digraphs and strong semicomplete bipartite digraphs. In this paper, we exhibit a family of strong 3-quasi-transitive digraphs distinct from strong semicomplete digraphs and strong semicomplete bipartite digraphs and provide a complete characterization of strong 3-quasi-transitive digraphs.     

Kings in locally semicomplete digraphs

A k‐king in a digraph D is a vertex which can reach every other vertex by a directed path of length at most k. We consider k‐kings in locally semicomplete digraphs and mainly prove that all strong locally semicomplete digraphs which are not round decomposable contain a 2‐king. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 279–287, 2010     

Existence of openly disjoint circuits through a vertex

We deal with conditions for a digraph of minimum degree r which imply the existence of a vertex x contained in r circuits which have pairwise only x in common. In particular, we give some positive answers to a question of P. Seymour, whether an r‐regular digraph has a vertex x which is contained in r circuits pairwise disjoint except for x, and show that the answer, in general, is negative. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 93–105, 2010     

SUPER EDGE-CONNECTIVITY OF DE BRUIJN AND KAUTZ UNDIRECTED GRAPHS

The super edge-connectivity of a graph is an important parameter to measure fault-tolerance of interconnection networks. This note shows that the Kautz undirected graph is super edge-connected,and provides a short proof of Lue and Zhang‘s result on super edge-connectivity of the de Bruijn undirected graph.     

n重线有向图的超连通性

本文证明了，在最小度至少为3的前提下超弧连通有向图的迭代线图是超点连通的．作为推论，我们得到了Kautz网络和de Bruijn网络的超点连通性和超弧连通性．     

有向循环图寻径控制

有向循环图 G(N ;1 ,s)作为有向双环网的图论模型备受关注 .本文将图的点集分划为几个不交子集 ,找到任意节点对之间路径沿跳长为 1和跳长为 s的边数的上确界 .找到了判断节点对间最短路径的充要条件 ,利用点集的分布特征设计了一个最优寻径算法 .对双环网络的容错路径进行了深入研究 ,给出了容错直径公式 ,提出了一个最优容错路径算法 .     

Isomorphisms of Cayley Digraphs of Infinite Abelian Groups

ＩｓｏｍｏｒｐｈｉｓｍｓｏｆＣａｙｌｅｙＤｉｇｒａｐｈｓｏｆＩｎｆｉｎｉｔｅＡｂｅｌｉａｎＧｒｏｕｐｓ￥ＭｅｎｇＪｉｘｉａｎｇ（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＸｉｎｊｉａｎｇＵｎｉｖｅｒｓｉｔｙ，Ｕｒｕｍｃｈｉ，８３００４６）Ａｂｓ...