Signed domination numbers of directed graphs

The concept of signed domination number of an undirected graph (introduced by J. E. Dunbar, S. T. Hedetniemi, M. A. Henning and P. J. Slater) is transferred to directed graphs. Exact values are found for particular types of tournaments. It is proved that for digraphs with a directed Hamiltonian cycle the signed domination number may be arbitrarily small.     

Digraph searching, directed vertex separation and directed pathwidth

The four digraph search models, directed search, undirected search, strong search, and weak search, are studied in this paper. There are three types of actions for searchers in these models: placing, removing, and sliding. The four models differ in the abilities of searchers and intruders depending on whether or not they must obey the edge directions when they move along the directed edges. In this paper, we investigate the relationships between these search models. We introduce the concept of directed vertex separation for digraphs. We also discuss the properties of directed vertex separation, and investigate the relations between directed vertex separation, directed pathwidth and search numbers in different search models.     

Acyclic systems of representatives and acyclic colorings of digraphs

A natural digraph analog of the graph theoretic concept of “an independent set” is that of “an acyclic set of vertices,” namely a set not spanning a directed cycle. By this token, an analog of the notion of coloring of a graph is that of decomposition of a digraph into acyclic sets. We extend some known results on independent sets and colorings in graphs to acyclic sets and acyclic colorings of digraphs. In particular, we prove bounds on the topological connectivity of the complex of acyclic sets, and using them we prove sufficient conditions for the existence of acyclic systems of representatives of a system of sets of vertices. These bounds generalize a result of Tardos and Szabó. We prove a fractional version of a strong‐acyclic‐coloring conjecture for digraphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 177–189, 2008     

对称本原图的集指数与本原简单图的广义上指数的极图

一个有向图D称为本原的，如果存在某个正整数k，使得对于D中的任一点x到任一点y都有长为k的途径，这样的正整数k中的最小者称为D的本原指数，作为本原指数概念的推广，R．A．Brualdi和柳柏濂于1990年引入了本原有向图的广义本原指数的新概念，本文给出了对称本原图的集指数的一些性质，并对本原简单图的广义上指数的极图进行了完全刻划。     

Split digraphs

We generalize the class of split graphs to the directed case and show that these split digraphs can be identified from their degree sequences. The first degree sequence characterization is an extension of the concept of splittance to directed graphs, while the second characterization says a digraph is split if and only if its degree sequence satisfies one of the Fulkerson inequalities (which determine when an integer-pair sequence is digraphic) with equality.     

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.     

若干有向图的SAS-全染色

提出了有向图的SAS-全染色的概念,有向图D的SAS-全染色是D的一个正常全染色,若对D中点染色来说,不存在长为3的2色有向路.对D中弧染色来说,不存在长为4的2色有向路.并定义了有向图D的SAS-全色数,记为(D).用构造染色的方法给出了一些特殊有向图(有向路,有向圈,定向轮,定向扇,有向双星)的SAS-全色数.     

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 complexity of Minimum Leaf Out-Branching problem

Given a digraph D, the Minimum Leaf Out-Branching problem (MinLOB) is the problem of finding in D an out-branching with the minimum possible number of leaves, i.e., vertices of out-degree zero. Gutin, Razgon and Kim [G. Gutin, I. Razgon, E.J. Kim, Minimum leaf out-branching problems, in: Proc. 4th International Conference on Algorithmic Aspects in Information and Management, AAIM’08, in: Lect. Notes Comput. Sci., vol. 5034 2008, pp. 235-246] proved that MinLOB is polynomial time solvable for acyclic digraphs which are exactly the digraphs of directed path-width (DAG-width, directed tree-width, respectively) 0. We investigate how much one can extend this polynomiality result. We prove that already for digraphs of directed path-width (directed tree-width, DAG-width, respectively) 1, MinLOB is NP-hard. On the other hand, we show that for digraphs of restricted directed tree-width (directed path-width, DAG-width, respectively) and a fixed integer k, the problem of checking whether there is an out-branching with at most k leaves is polynomial time solvable.     

A Spectral Study of the Manhattan Networks

The multidimensional Manhattan networks are a family of digraphs with many appealing properties, such as vertex symmetry (in fact they are Cayley digraphs), easy routing, Hamiltonicity, and modular structure. From the known structural properties of these digraphs, we fully determine their spectra, which always contain the spectra of hypercubes. In particular, in the standard (two-dimensional) case it is shown that their line digraph structure imposes the presence of the zero eigenvalue with a large multiplicity.     

The spectra of Manhattan street networks

The multidimensional Manhattan street networks constitute a family of digraphs with many interesting properties, such as vertex symmetry (in fact they are Cayley digraphs), easy routing, Hamiltonicity, and modular structure. From the known structural properties of these digraphs, we determine their spectra, which always contain the spectra of hypercubes. In particular, in the standard (two-dimensional) case it is shown that their line digraph structure imposes the presence of the zero eigenvalue with a large multiplicity.     

HSAGA and its application for the construction of near-Moore digraphs

The degree/diameter problem is to determine the largest graphs or digraphs of given maximum degree and given diameter. This paper deals with directed graphs. General upper bounds, called Moore bounds, exist for the largest possible order of such digraphs of maximum degree d and given diameter k. It is known that simulated annealing and genetic algorithm are effective techniques to identify global optimal solutions.This paper describes our attempt to build a Hybrid Simulated Annealing and Genetic Algorithm (HSAGA) that can be used to construct large digraphs. We present our new results obtained by HSAGA, as well as several related open problems.     

Some constructions of highly arc-transitive digraphs

We construct infinite highly arc-transitive digraphs with finite out-valency and whose sets of descendants are digraphs which have a homomorphism onto a directed (rooted) tree. Some of these constructions are based on [4] and [5], and are shown to have universal reachability relation.     

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.     

Hamiltonicity of large generalized de Bruijn cycles

In this article, we determine when the large generalized de Bruijn cycles are Hamiltonian. These digraphs have been introduced by Gómez, Padró and Pérennes as large interconnection networks with small diameter and they are a family of generalized cycles. They are Kronecker products of generalized de Bruijn digraphs and dicycles.     

HAMILTONIAN CYCLES AND DECOMPOSITIONS OFCAYLEY DIGRAPHS OF FINITE ABELIAN GROUPS

In this paper, Hamiltonian cycles and decompositions of Cayley digraphs are investigat-ed. Sufficient conditions are given for these two problems respectively. Furthermore, the conditions are also necesaary for 2-regular Cayley disraphs, In addition, some known results about theCartesian products of two directed cycles are also deduced.     

Ihara zeta functions of digraphs

After defining and exploring some of the properties of Ihara zeta functions of digraphs, we improve upon Kotani and Sunada’s bounds on the poles of Ihara zeta functions of undirected graphs by considering digraphs whose adjacency matrices are directed edge matrices.     

Cliques that are tolerance digraphs

In this paper, we study directed graph versions of tolerance graphs, in particular, the class of totally bounded bitolerance digraphs and several subclasses. When the underlying graph is complete, we prove that the classes of totally bounded bitolerance digraphs and interval catch digraphs are equal, and this implies a polynomial-time recognition algorithm for the former class. In addition, we give examples (whose underlying graphs are complete) to separate every other pair of subclasses, and one of these provides a counterexample to a conjecture of Maehara (1984).     

Enumeration and generation of a class of regular digraphs

We study the class of directed graphs that have indegree = outdegree = 2 at every vertex. These digraphs can be decomposed uniquely into “alternating cycles”, we use this decomposition to present efficient techniques for counting and generating them. The number (up to isomorphism) of these digraphs and the number of connected ones on up to 20 vertices have been computed and are presented.     

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.