Arc transitive covering digraphs and their eigenvalues

We prove that every finite regular digraph has an arc-transitive covering digraph (whose arcs are equivalent under automorphisms) and every finite regular graph has a 2-arc-transitive covering graph. As a corollary, we sharpen C. D. Godsil's results on eigenvalues and minimum polynomials of vertex-transitive graphs and digraphs. Using Godsil's results, we prove, that given an integral matrix A there exists an arc-transitive digraph X such that the minimum polynomial of A divides that of X. It follows that there exist arc-transitive digraphs with nondiagonalizable adjacency matrices, answering a problem by P. J. Cameron. For symmetric matrices A, we construct a 2-arc-transitive graphs X.     

On Schreier graphs of gyrogroup actions

The notion of a group action can be extended to the case of gyrogroups. In this article, we examine a digraph and graph associated with a gyrogroup action on a finite nonempty set, called a Schreier digraph and graph. We show that algebraic properties of gyrogroups and gyrogroup actions such as being gyrocommutative, being transitive, and being fixed-point-free are reflected in their Schreier digraphs and graphs. We also prove graph-theoretic versions of the three fundamental theorems involving actions: the Cauchy–Frobenius lemma (also known as the Burnside lemma), the orbit-stabilizer theorem, and the orbit decomposition theorem. Finally, we make a connection between gyrogroup actions and actions of symmetric groups by evaluation via Schreier digraphs and graphs.     

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.     

Monotone Jónsson operations and near unanimity functions

We define nonextendible colored posets and zigzags of a poset. These notions are related to the earlier notions of gaps, holes, obstructions and zigzags considered by Duffus, Nevermann, Rival, Tardos and Wille. We establish some properties of zigzags. By using these properties we give a proof of the well known conjecture that states that any finite bounded poset which admits Jsson operations, also admits a near unanimity function. We also provide an infinite poset that shows that we cannot drop the finiteness in this conjecture.Presented by R. McKenzie.     

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.     

Upward planarity testing

Acyclic digraphs, such as the covering digraphs of ordered sets, are usually drawn upward, i.e., with the edges monotonically increasing in the vertical direction. A digraph is upward planar if it admits an upward planar drawing. In this survey paper, we overview the literature on the problem of upward planarity testing. We present several characterizations of upward planarity and describe upward planarity testing algorithms for special classes of digraphs, such as embedded digraphs and single-source digraphs. We also sketch the proof of NP-completeness of upward planarity testing.Research supported in part by the National Science Foundation under grant CCR-9423847.     

对称本原有向图广义重上指数的极图刻划

一个有向图Ｄ称为本原有向图,若存在某自然数ｋ,使Ｄ中任一点ｕ到任 一点ｖ都有长为ｋ之途径．若Ｄ是一个对称有向图,则Ｄ是本原的当且仅当Ｄ对 应的无向图连通且至少包含一个奇圈。文［２］给出了具有最小奇圈长ｒ的ｎ阶对称本 原有向图广义ｋ重上指数的最大数．本文将在此基础上,给出其极图的完全刻划．     

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.     

Locally semicomplete digraphs: A generalization of tournaments

In this paper we introduce a new class of directed graphs called locally semicomplete digraphs. These are defined to be those digraphs for which the following holds: for every vertex x the vertices dominated by x induce a semicomplete digraph and the vertices that dominate x induce a semicomplete digraph. (A digraph is semicomplete if for any two distinct vertices u and ν, there is at least one arc between them.) This class contains the class of semicomplete digraphs, but is much more general. In fact, the class of underlying graphs of the locally semi-complete digraphs is precisely the class of proper circular-arc graphs (see [13], Theorem 3). We show that many of the classic theorems for tournaments have natural analogues for locally semicomplete digraphs. For example, every locally semicomplete digraph has a directed Hamiltonian path and every strong locally semicomplete digraph has a Hamiltonian cycle. We also consider connectivity properties, domination orientability, and algorithmic aspects of locally semicomplete digraphs. Some of the results on connectivity are new, even when restricted to semicomplete digraphs.     

有向图反能量的一个注记

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

On finite reflexive homomorphism-homogeneous binary relational systems

A structure is called homogeneous if every isomorphism between finitely induced substructures of the structure extends to an automorphism of the structure. Recently, P. J. Cameron and J. Nešet?il introduced a relaxed version of homogeneity: we say that a structure is homomorphism-homogeneous if every homomorphism between finitely induced substructures of the structure extends to an endomorphism of the structure.In this paper, we consider finite homomorphism-homogeneous relational systems with one reflexive binary relation. We show that for a large part of such relational systems (bidirectionally connected digraphs; a digraph is bidirectionally connected if each of its connected components can be traversed by ?-paths) the problem of deciding whether the system is homomorphism-homogeneous is coNP-complete. Consequently, for this class of relational systems there is no polynomially computable characterization (unless P=NP). On the other hand, in case of bidirectionally disconnected digraphs we present the full characterization. Our main result states that if a digraph is bidirectionally disconnected, then it is homomorphism-homogeneous if and only if it is either a finite homomorphism-homogeneous quasiorder, or an inflation of a homomorphism-homogeneous digraph with involution (a specific class of digraphs introduced later in the paper), or an inflation of a digraph whose only connected components are and .     

Adjusted Interval Digraphs

Interval digraphs were introduced by West et al. They can be recognized in polynomial time and admit a characterization in terms of incidence matrices. Nevertheless, they do not have a forbidden structure characterization nor a low-degree polynomial recognition algorithm.We introduce a new class of ‘adjusted interval digraphs,’ obtained by a slight change in the definition. We show that, by contrast, these digraphs have a natural forbidden structure characterization, parallel to a characterization for undirected graphs, and admit a simple recognition algorithm. We relate adjusted interval digraphs to a list homomorphism problem. Each digraph H defines a corresponding list homomorphism problem L-HOM(H). We observe that if H is an adjusted interval digraph, then the problem L-HOM(H) is polynomial time solvable, and conjecture that for all other reflexive digraphs H the problem L-HOM(H) is NP-complete. We present some preliminary evidence for the conjecture, including a proof for the special case of semi-complete digraphs.     

一类特殊的本原不可幂对称带号有向图的基指数的上界

一个本原不可幂带号有向图s的基指数l(s)是这样的最小正整数l,使得在s中,从任意一点u到任意一点v都有一对长为l的sssD途径.本文研究了n阶最小奇圈长为r的本原不可幂对称带号有向图的基指数,给出了这类有向图的基指数的最大值.     

正圆有向图中的弧不相交的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的猜想成立.     

Linear arboricity of regular digraphs

A linear directed forest is a directed graph in which every component is a directed path.The linear arboricity la(D) of a digraph D is the minimum number of linear directed forests in D whose union covers all arcs of D. For every d-regular digraph D, Nakayama and P′eroche conjecture that la(D) = d + 1. In this paper, we consider the linear arboricity for complete symmetric digraphs,regular digraphs with high directed girth and random regular digraphs and we improve some wellknown results. Moreover, we propose a more precise conjecture about the linear arboricity for regular digraphs.     

On Vosperian and Superconnected Vertex-Transitive Digraphs

We investigate the structure of a digraph having a transitive automorphism group where every cutset of minimal cardinality consists of all successors or all predecessors of some vertex. We give a complete characterization of vosperian arc-transitive digraphs. It states that an arc-transitive strongly connected digraph is vosperian if and only if it is irreducible. In particular, this is the case if the degree is coprime with the order of the digraph. We give also a complete characterization of vosperian Cayley digraphs and a complete characterization of irreducible superconnected Cayley digraphs. These two last characterizations extend the corresponding ones in Abelian Cayley digraphs and the ones in the undirected case.     

具有最小弧数且基指数为3的本原不可幂对称无环带号有向图

Let S be a primitive non-powerful symmetric loop-free signed digraph on even n vertices with base 3 and minimum number of arcs. In [Lihua YOU, Yuhan WU. Primitive non-powerful symmetric loop-free signed digraphs with given base and minimum number of arcs. Linear Algebra Appl., 2011, 434(5), 1215-1227], authors conjectured that D is the underlying digraph of S with exp(D) = 3 if and only if D is isomorphic to ED n,3,3 , where ED n,3,3 = (V, A) is a digraph with V = {1, 2, . . . , n}, A = {(1, i), (i, 1) | 3≤i≤n} ∪ {(2i-1, 2i), (2i, 2i-1) | 2≤i≤ n/2 } ∪ {(2, 3), (3, 2), (2, 4), (4, 2)}). In this paper, we show the conjecture is true and completely characterize the underlying digraphs which have base 3 and the minimum number of arcs.     

Packing strong subgraph in digraphs

In this paper, we study two types of strong subgraph packing problems in digraphs, including internally disjoint strong subgraph packing problem and arc-disjoint strong subgraph packing problem. These problems can be viewed as generalizations of the famous Steiner tree packing problem and are closely related to the strong arc decomposition problem. We first prove the NP-completeness for the internally disjoint strong subgraph packing problem restricted to symmetric digraphs and Eulerian digraphs. Then we get inapproximability results for the arc-disjoint strong subgraph packing problem and the internally disjoint strong subgraph packing problem. Finally we study the arc-disjoint strong subgraph packing problem restricted to digraph compositions and obtain some algorithmic results by utilizing the structural properties.     

Making choices with a binary relation: Relative choice axioms and transitive closures

This article presents an axiomatic analysis of the best choice decision problem from a reflexive crisp binary relation on a finite set (a digraph). With respect to a transitive digraph, optimality and maximality are usually accepted as the best fitted choice axioms to the intuitive notion of best choice. However, beyond transitivity (resp. acyclicity), optimality and maximality can characterise distinct choice sets (resp. empty sets). Accordingly, different and rather unsatisfying concepts have appeared, such as von Neumann–Morgenstern domination, weak transitive closure and kernels. Here, we investigate a new family of eight choice axioms for digraphs: relative choice axioms. Within choice theory, these axioms generalise top-cycle for tournaments, gocha, getcha and rational top-cycle for complete digraphs. We present their main properties such as existence, uniqueness, idempotence, internal structure, and cross comparison. We then show their strong relationship with optimality and maximality when the latter are not empty. Otherwise, these axioms identify a non-empty choice set and underline conflicts between chosen elements in strict preference circuits. Finally, we exploit the close link between this family and transitive closures to compute choice sets in linear time, followed by a relevant practical application.     

Unit and proper bitolerance digraphs

In this paper we prove that the following statements about a directed graph G→ are equivalent. (1) G→ is a unit bitolerance digraph, (2) G→ is a proper bitolerance digraph, and (3) the digraph obtained by reversing all arc directions of G→ is an interval catch digraph (also known as a point-core digraph). This result combined with known algorithms for recognizing interval catch digraphs, gives the first known polynomial-time algorithm for recognizing a class of (bi)tolerance digraphs. © 1997 John Wiley & Sons, Inc.