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 even factorizations and the chromatic index of the Kautz and de Bruijn digraphs

Motivated by the problem of designing large packet radio networks, we show that the Kautz and de Bruijn digraphs with in- and outdegree d have arc-chromatic index 2d. In order to do this, we introduce the concept of even 1-factorizations. An even 1-factor of a digraph is a spanning subgraph consisting of vertex disjoint loops and even cycles; an even 1-factorization is a partition of the arcs into even 1-factors. We prove that if a digraph admits an even 1-factorization, then so does its line digraph. (In fact, we show that the line digraph admits an even 1-factorization even under a weaker assumption discussed below.) As a consequence, we derive the above property of the Kautz and de Bruijn digraphs relevant to packet radio networks. © 1993 John Wiley & Sons, Inc.     

正圆有向图中的弧不相交的Hamilton路和圈

2012年,Bang-Jensen和Huang(J.Combin.Theory Ser.B.2012,102:701-714)证明了2-弧强的局部半完全有向图可以分解为两个弧不相交的强连通生成子图当且仅当D不是偶圈的二次幂,并提出了任意3-强的局部竞赛图中包含两个弧不相交的Hamilton圈的猜想.主要研究正圆有向图中的弧不相交的Hamilton路和Hamilton圈,并证明了任意3-弧强的正圆有向图中包含两个弧不相交的Hamilton圈和任意4-弧强的正圆有向图中包含一个Hamilton圈和两个Hamilton路,使得它们两两弧不相交.由于任意圆有向图一定是正圆有向图,所得结论可以推广到圆有向图中.又由于圆有向图是局部竞赛图的子图类,因此所得结论说明对局部竞赛图的子图类――圆有向图,Bang-Jensen和Huang的猜想成立.     

Disjoint quasi‐kernels in digraphs

A quasi‐kernel in a digraph is an independent set of vertices such that any vertex in the digraph can reach some vertex in the set via a directed path of length at most two. Chvátal and Lovász proved that every digraph has a quasi‐kernel. Recently, Gutin et al. raised the question of which digraphs have a pair of disjoint quasi‐kernels. Clearly, a digraph has a pair of disjoint quasi‐kernels cannot contain sinks, that is, vertices of outdegree zero, as each such vertex is necessarily included in a quasi‐kernel. However, there exist digraphs which contain neither sinks nor a pair of disjoint quasi‐kernels. Thus, containing no sinks is not sufficient in general for a digraph to have a pair of disjoint quasi‐kernels. In contrast, we prove that, for several classes of digraphs, the condition of containing no sinks guarantees the existence of a pair of disjoint quasi‐kernels. The classes contain semicomplete multipartite, quasi‐transitive, and locally semicomplete digraphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:251‐260, 2008     

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.     

强哈密尔顿连通有向图的一个注记

利用收缩技术,证明了1)阶为n=2k且最小半度至少是k的有向图D是强哈密尔顿连通的,除非D属于某些图类;2)2强连通且包含n个顶点、(n-1)(n-2)+4条弧的有向图是强哈密尔顿连通的,除非D属于某些图类.     

Quasi-transitive digraphs

A digraph is quasi-transitive if there is a complete adjacency between the inset and the outset of each vertex. Quasi-transitive digraphs are interseting because of their relation to comparability graphs. Specifically, a graph can be oriented as a quasi-transitive digraph if and only if it is a comparability graph. Quasi-transitive digraphs are also of interest as they share many nice properties of tournaments. Indeed, we show that every strongly connected quasi-transitive digraphs D on at least four vertices has two vertices v₁ and v₂ such that D – v_i is strongly connected for i = 1, 2. A result of tournaments on the existence of a pair of arc-disjoint in- and out-branchings rooted at the same vertex can also be extended to quasi-transitive digraphs. However, some properties of tournaments, like hamiltonicity, cannot be extended directly to quasi-transitive digraphs. Therefore we characterize those quasi-transitive digraphs which have a hamiltonian cycle, respectively a hamiltonian path. We show the existence of highly connected quasi-transitive digraphs D with a factor (a collection of disjoint cycles covering the vertex set of D), which have a cycle of every length 3 ≦ k ≦ |V(D)| ? 1 through every vertex and yet they are not hamiltonian. Finally we characterize pancyclic and vertex pancyclic quasi-transitive digraphs. © 1995, John Wiley & Sons, Inc.     

Kernels by properly colored paths in arc-colored digraphs

A kernel by properly colored paths of an arc-colored digraph $D$ is a set $S$ of vertices of $D$ such that (i) no two vertices of $S$ are connected by a properly colored directed path in $D$, and (ii) every vertex outside $S$ can reach $S$ by a properly colored directed path in $D$. In this paper, we conjecture that every arc-colored digraph with all cycles properly colored has such a kernel and verify the conjecture for digraphs with no intersecting cycles, semi-complete digraphs and bipartite tournaments, respectively. Moreover, weaker conditions for the latter two classes of digraphs are given.     

A Note on Automorphisms of Coset Digraphs

This paper considers automorphism groups of finite digraphs whose edge set can be decomposed into oriented cycles. The cycles are coloured in such a way that any two cycles of equal colour are vertex-disjoint. A ${\cal P}$ -automorphism is defined to be an automorphism of the underlying digraph which preserves the decomposition ${\cal P}$ into coloured cycles. In this paper the isomorphism class of the group of ${\cal P}$ -automorphisms is determined for each decomposition of ${\cal P}$ . The results are obtained using a representation of coloured digraphs as coset digraphs of groups defined by the colouring.     

Line digraphs and the Moore-Penrose inverse

Various characterizations of line digraphs and of Boolean matrices possessing a Moore-Penrose inverse are used to show that a square Boolean matrix has a Moore-Penrose inverse if and only if it is the adjacency matrix of a line digraph. A similar relationship between a nonsquare Boolean matrix and a bipartite graph is also given.     

Some sufficient conditions for the existence of kernels in infinite digraphs

A kernel N of a digraph D is an independent set of vertices of D such that for every w∈V(D)−N there exists an arc from w to N. If every induced subdigraph of D has a kernel, D is said to be a kernel perfect digraph. D is called a critical kernel imperfect digraph when D has no kernel but every proper induced subdigraph of D has a kernel. If F is a set of arcs of D, a semikernel modulo F of D is an independent set of vertices S of D such that for every z∈V(D)−S for which there exists an (S,z)-arc of D−F, there also exists an (z,S)-arc in D. In this work we show sufficient conditions for an infinite digraph to be a kernel perfect digraph, in terms of semikernel modulo F. As a consequence it is proved that symmetric infinite digraphs and bipartite infinite digraphs are kernel perfect digraphs. Also we give sufficient conditions for the following classes of infinite digraphs to be kernel perfect digraphs: transitive digraphs, quasi-transitive digraphs, right (or left)-pretransitive digraphs, the union of two right (or left)-pretransitive digraphs, the union of a right-pretransitive digraph with a left-pretransitive digraph, the union of two transitive digraphs, locally semicomplete digraphs and outward locally finite digraphs.     

On large vertex-symmetric digraphs

There is special interest in the design of large vertex-symmetric graphs and digraphs as models of interconnection networks for implementing parallelism. In these systems, a large number of nodes are connected with relatively few links and short paths between the nodes, and each node may execute the same communication software without modifications.In this paper, a method for obtaining new general families of large vertex-symmetric digraphs is put forward. To be more precise, from a k-reachable vertex-symmetric digraph and another (k+1)-reachable digraph related to the previous one, and using a new special composition of digraphs, new families of vertex-symmetric digraphs with small diameter are presented. With these families we obtain new vertex-symmetric digraphs that improve various values of the table of the largest known vertex-symmetric (Δ,D)-digraphs. The paper also contains the (Δ,D)-table for vertex-symmetric digraphs, for Δ≤13 and D≤12.     

Highly Arc-Transitive Digraphs With No Homomorphism Onto <Emphasis Type="Bold">Z</Emphasis>

In an infinite digraph D, an edge e' is reachable from an edge e if there exists an alternating walk in D whose initial and terminal edges are e and e'. Reachability is an equivalence relation and if D is 1-arc-transitive, then this relation is either universal or all of its equivalence classes induce isomorphic bipartite digraphs. In Combinatorica, 13 (1993), Cameron, Praeger and Wormald asked if there exist highly arc-transitive digraphs (apart from directed cycles) for which the reachability relation is not universal and which do not have a homomorphism onto the two-way infinite directed path (a Cayley digraph of Z with respect to one generator). In view of an earlier result of Praeger in Australas. J. Combin., 3 (1991), such digraphs are either locally infinite or have equal in- and out-degree. In European J. Combin., 18 (1997), Evans gave an affirmative answer by constructing a locally infinite example. For each odd integer n >= 3, a construction of a highly arc-transitive digraph without property Z satisfying the additional properties that its in- and out-degree are equal to 2 and that the reachability equivalence classes induce alternating cycles of length 2n, is given. Furthermore, using the line digraph operator, digraphs having the above properties but with alternating cycles of length 4 are obtained. Received April 12, 1999 Supported in part by "Ministrstvo za šolstvo, znanost in šport Slovenije", research program PO-0506-0101-99.     

有向图反能量的一个注记

有向图的反能量是指有向图的反邻接矩阵的能量.本文利用有向图的运算构造出了几类有向图,它们中的每一个都满足有向图的反能量等于其底图的能量.部分回答了Adiga等人在文[The skew energy of a digraph,Linear Algebra Appl.,2010,432:1825-1835]中提出的一个公开问题.     

A Characterization of Locally Semicomplete CKI-digraphs

A digraph is locally-in semicomplete if for every vertex of D its in-neighborhood induces a semicomplete digraph and it is locally semicomplete if for every vertex of D the in-neighborhood and the out-neighborhood induces a semicomplete digraph. The locally semicomplete digraphs where characterized in 1997 by Bang-Jensen et al. and in 1998 Bang-Jensen and Gutin posed the problem if finding a kernel in a locally-in semicomplete digraph is polynomial or not. A kernel of a digraph is a set of vertices, which is independent and absorbent. A digraph D such that every proper induced subdigraph of D has a kernel is said to be critical kernel imperfect digraph (CKI-digraph) if the digraph D does not have a kernel. A digraph without an induced CKI-digraph as a subdigraph does have a kernel. We characterize the locally semicomplete digraphs, which are CKI. As a consequence of this characterization we conclude that determinate whether a locally semicomplete digraph is a CKI-digraph or not, is polynomial.     

The Twin Domination Numb er of Strong Pro duct of Digraphs

Let γ*(D) denote the twin domination number of digraph D and let D_1  D_2 denote the strong product of D_1 and D_2. In this paper, we obtain that the twin domination number of strong product of two directed cycles of length at least 2.Furthermore, we give a lower bound of the twin domination number of strong product of two digraphs, and prove that the twin domination number of strong product of the complete digraph and any digraph D equals the twin domination number of D.     

DAG‐Width and Circumference of Digraphs

We prove that every digraph of circumference l has DAG‐width at most l. This is best possible and solves a recent conjecture from S. Kintali (ArXiv:1401.2662v1 [math.CO], January 2014).¹ As a consequence of this result we deduce that the k‐linkage problem is polynomially solvable for every fixed k in the class of digraphs with bounded circumference. This answers a question posed in J. Bang‐Jensen, F. Havet, and A. K. Maia (Theor Comput Sci 562 (2014), 283–303). We also prove that the weak k‐linkage problem (where we ask for arc‐disjoint paths) is polynomially solvable for every fixed k in the class of digraphs with circumference 2 as well as for digraphs with a bounded number of disjoint cycles each of length at least 3. The case of bounded circumference digraphs is still open. Finally, we prove that the minimum spanning strong subdigraph problem is NP‐hard on digraphs of DAG‐width at most 5.     

Locally-finite connected-homogeneous digraphs

A digraph is connected-homogeneous if any isomorphism between finite connected induced subdigraphs extends to an automorphism of the digraph. We consider locally-finite connected-homogeneous digraphs with more than one end. In the case that the digraph embeds a triangle we give a complete classification, obtaining a family of tree-like graphs constructed by gluing together directed triangles. In the triangle-free case we show that these digraphs are highly arc-transitive. We give a classification in the two-ended case, showing that all examples arise from a simple construction given by gluing along a directed line copies of some fixed finite directed complete bipartite graph. When the digraph has infinitely many ends we show that the descendants of a vertex form a tree, and the reachability graph (which is one of the basic building blocks of the digraph) is one of: an even cycle, a complete bipartite graph, the complement of a perfect matching, or an infinite semiregular tree. We give examples showing that each of these possibilities is realised as the reachability graph of some connected-homogeneous digraph, and in the process we obtain a new family of highly arc-transitive digraphs without property Z.     

Double-super-connected digraphs

A strongly connected digraph D is said to be super-connected if every minimum vertex-cut is the out-neighbor or in-neighbor set of a vertex. A strongly connected digraph D is said to be double-super-connected if every minimum vertex-cut is both the out-neighbor set of a vertex and the in-neighbor set of a vertex. In this paper, we characterize the double-super-connected line digraphs, Cartesian product and lexicographic product of two digraphs. Furthermore, we study double-super-connected Abelian Cayley digraphs and illustrate that there exist double-super-connected digraphs for any given order and minimum degree.