On critically connected digraphs

A digraph is called critically connected if it is connected, but the deletion of any vertex destroys the connectivity. We prove that every critically connected finite digraph has at least two vertices of outdegree one. As an application, we show that for n ≧ 2, there is no n-connected, non-complete, finite digraph such that the deletion of any n vertices results in a disconnected digraph.     

Using principal eigenvectors of adjacency matrices with added diagonal weights to compose centrality measures and identify bowtie structures for a digraph

Principal eigenvectors of adjacency matrices are often adopted as measures of centrality for a graph or digraph. However, previous principal-eigenvector-like measures for a digraph usually consider only the strongly connected component whose adjacency submatrix has the largest eigenvalue. In this paper, for each and every strongly connected component in a digraph, we add weights to diagonal elements of its member nodes in the adjacency matrix such that the modified matrix will have the new unique largest eigenvalue and corresponding principal eigenvectors. Consequently, we use the new principal eigenvectors of the modified matrices, based on different strongly connected components, not only to compose centrality measures but also to identify bowtie structures for a digraph.     

On the number of noncritical vertices in strongly connected digraphs

By definition, a vertex w of a strongly connected (or, simply, strong) digraph D is noncritical if the subgraph D — w is also strongly connected. We prove that if the minimal out (or in) degree k of D is at least 2, then there are at least k noncritical vertices in D. In contrast to the case of undirected graphs, this bound cannot be sharpened, for a given k, even for digraphs of large order. Moreover, we show that if the valency of any vertex of a strong digraph of order n is at least 3/4n, then it contains at least two noncritical vertices. The proof makes use of the results of the theory of maximal proper strong subgraphs established by Mader and developed by the present author. We also construct a counterpart of this theory for biconnected (undirected) graphs.     

The closure of the set of roots of strongly connected reliability polynomials is the entire complex plane

The strongly connected reliabilityscRel(D,p) of a digraph D is the probability that the spanning subgraph of D consisting of the operational arcs is strongly connected, given that the vertices always operate, but each arc is independently operational with probability p∈[0,1]. We show that the closure of the set of roots of strongly connected reliability polynomials is the whole complex plane.     

k-Walk-Regular Digraphs

In this paper,we define a class of strongly connected digraph,called the k-walk- regular digraph,study some properties of it,provide its some algebraic characterization and point out that the 0-walk-regular digraph is the same as the walk-regular digraph discussed by Liu and Lin in 2010 and the D-walk-regular digraph is identical with the weakly distance-regular digraph defined by Comellas et al in 2004.     

On the number of connected convex subgraphs of a connected acyclic digraph

A digraph D is connected if the underlying undirected graph of D is connected. A subgraph H of an acyclic digraph D is convex if there is no directed path between vertices of H which contains an arc not in H. We find the minimum and maximum possible number of connected convex subgraphs in a connected acyclic digraph of order n. Connected convex subgraphs of connected acyclic digraphs are of interest in the area of modern embedded processors technology.     

Cycle factors in strongly connected local tournaments

A digraph without loops, multiple arcs and directed cycles of length two is called a local tournament if the set of in-neighbors as well as the set of out-neighbors of every vertex induces a tournament. A digraph is 2-connected if the removal of an arbitrary vertex results in a strongly connected digraph.In 2004 and 2005, Li and Shu investigated the structure of strongly connected, but not 2-connected tournaments. Using their structural results they were able to give sufficient conditions for a strongly connected tournament T to have complementary cycles or a k-cycle factor, i.e. a set of k vertex disjoint cycles that span the vertex set of T.Inspired by the articles of Li and Shu we develop in this paper the structure necessary for a strongly connected local tournament to be not cycle complementary. Using this structure, we are able to generalize and transfer various results of Li and Shu to the class of local tournaments.     

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.     

Every finite strongly connected digraph of stability 2 has a Hamiltonian path

Two circuits C₁ and C₂ in a digraph are called consistent circuits if and only if their intersection is either empty, a singleton or a subpath of both C₁ and C₂. It is proved that Every finite strongly connected digraph of G of stability at most 2 is spanned by two consistent circuits. As a consequence, every finite strongly connected digraph of stability two has a Hamiltonian path.     

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.     

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.     

Fast parallel strong orientation of mixed graphs and related augmentation problems

The strong orientation problem is: Given an undirected graph, G, assign orientations to its edges so that the resulting directed graph is strongly connected. Robbins showed when such an orientation exists. A generalization of this problem is when the input graph is mixed (i.e., contains some directed and some undirected edges). Boesch and Tindell gave necessary and sufficient conditions for a strong orientation to exist in a mixed graph. In this paper we give an NC algorithm for constructing a strong orientation for a given mixed graph after determining if it exists. We also give an NC algorithm for adding a minimum set of arcs to a mixed graph to make it strongly orientable. We give simplified NC algorithms for the following special cases: find minimum augmentations to make a digraph strongly connected and to make an undirected graph bridge-connected. All the algorithms presented run within the time and processor bounds required for computing the transitive closure of a digraph.     

有向跳图的生成欧拉子有向图

一个有向多重图D的跳图$J(D)$是一个顶点集为$D$的弧集,其中$(a,b)$是$J(D)$的一条弧当且仅当存在有向多重图$D$中的顶点$u_1$, $v_1$, $u_2$, $v_2$,使得$a=(u_1,v_1)$, $b=(u_2,v_2)$ 并且$v_1\neq u_2$.本文刻画了有向多重图类$\mathcal{H}_1$和$\mathcal{H}_2$,并证明了一个有向多重图$D$的跳图$J(D)$是强连通的当且仅当$D\not\in \mathcal{H}_1$.特别地, $J(D)$是弱连通的当且仅当$D\not\in \mathcal{H}_2$.进一步, 得到以下结果: (i) 存在有向多重图类$\mathcal{D}$使得有向多重图$D$的强连通跳图$J(D)$是强迹连通的当且仅当$D\not\in\mathcal{D}$. (ii) 每一个有向多重图$D$的强连通跳图$J(D)$是弱迹连通的,因此是超欧拉的. (iii) 每一个有向多重图D的弱连通跳图$J(D)$含有生成迹.     

Super-connected arc-transitive digraphs

A digraph is said to be super-connected if every minimum vertex cut is the out-neighbor set or in-neighbor set of a vertex. A digraph is said to be reducible, if there are two vertices with the same out-neighbor set or the same in-neighbor set. In this paper, we prove that a strongly connected arc-transitive oriented graph is either reducible or super-connected. Furthermore, if this digraph is also an Abelian Cayley digraph, then it is super-connected.     

On pancyclic digraphs

We show that a strongly connected digraph with n vertices and minimum degree ? n is pancyclic unless it is one of the graphs K_p,p. This generalizes a result of A. Ghouila-Houri. We disprove a conjecture of J. A. Bondy by showing that there exist hamiltonian digraphs with n vertices and $\text{1}\text{2}\text{n(n + 1) – 3}$ edges which are not pancyclic. We show that any hamiltonian digraph with n vertices and at least $\text{1}\text{2}\text{n(n + 1) – 1}$ edges is pancyclic and we give some generalizations of this result. As applications of these results we determine the minimal number of edges required in a digraph to guarantee the existence of a cycle of length k, k ? 2, and we consider the corresponding problem where the digraphs under consideration are assumed to be strongly connected.     

Bigraphs versus digraphs via matrices

It was observed by Dulmage and Mendelsohn in their work on matrix reducibility that there is a one-to-one correspondence between bigraphs and digraphs determined by the utilization of the adjacency matrix. In this semiexpository paper we explore the interaction between this correspondence and a theory of matrix decomposability that is developed in several different articles. These results include: (a) a characterization of those bipartite graphs that can be labeled so that the resulting digraph is symmetric; (b) a criterion for the bigraph of a symmetric digraph to be connected; (c) a necessary and sufficient condition for a square binary matrix to be fully indecomposable in terms of its associated bigraph, and (d) matrix criteria for a digraph to be strongly, unilaterally, or weakly connected. We close with an unsolved extermal problem on the number of components of the bigraph of various orientations of a given graph. This leads to new amusing characterizations of trees and bigraphs. Dedicated to the graph-theoretic partnership of Lloyd Dulmage and Nathan Mendelsohn.     

On non‐Hamiltonian circulant digraphs of outdegree three

We construct infinitely many connected, circulant digraphs of outdegree three that have no Hamiltonian circuit. All of our examples have an even number of vertices, and our examples are of two types: either every vertex in the digraph is adjacent to two diametrically opposite vertices, or every vertex is adjacent to the vertex diametrically opposite to itself. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 319–331, 1999     

Hypotraceable digraphs

A hypotraceable digraph is a digraph D = (V, E) which is not traceable, i.e., does not contain a (directed)Hamiltonian path, but for which D - v is traceable for all ve ∈ V. We prove that a hypotraceable digraph of order n exists iff n ≥ 7 and that for each k ≥ 3 there are infinitely many hypotraceable oriented graphs with a source and a sink and precisely k strong components. We also show that there are strongly connected hypotraceable oriented graphs and that there are hypotraceable digraphs with precisely two strong components one of which is a source or a sink. Finally, we prove that hypo-Hamiltonian and hypotraceable digraphs may contain large complete subdigraphs.     

The diameter of randomly perturbed digraphs and some applications

The central observation of this paper is that if εn random arcs are added to any n‐node strongly connected digraph with bounded degree then the resulting graph has diameter 𝒪(lnn) with high probability. We apply this to smoothed analysis of algorithms and property testing. Smoothed Analysis: Recognizing strongly connected digraphs is a basic computational task in graph theory. Even for digraphs with bounded degree, it is NL‐complete. By XORing an arbitrary bounded degree digraph with a sparse random digraph R ∼ 𝔻_n,ε/n we obtain a “smoothed” instance. We show that, with high probability, a log‐space algorithm will correctly determine if a smoothed instance is strongly connected. We also show that if NL ⫅̸ almost‐L then no heuristic can recognize similarly perturbed instances of (s,t)‐connectivity. Property Testing: A digraph is called k‐linked if, for every choice of 2k distinct vertices s₁,…,s_k,t₁,…,t_k, the graph contains k vertex disjoint paths joining s_r to t_r for r = 1,…,k. Recognizing k‐linked digraphs is NP‐complete for k ≥ 2. We describe a polynomial time algorithm for bounded degree digraphs, which accepts k‐linked graphs with high probability, and rejects all graphs that are at least εn arcs away from being k‐linked. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

On the number of cycles in local tournaments

A digraph without loops, multiple arcs and directed cycles of length two is called a local tournament if the set of in-neighbors as well as the set of out-neighbors of every vertex induces a tournament. A vertex of a strongly connected digraph is called a non-separating vertex if its removal preserves the strong connectivity of the digraph in question.In 1990, Bang-Jensen showed that a strongly connected local tournament does not have any non-separating vertices if and only if it is a directed cycle. Guo and Volkmann extended this result in 1994. They determined the strongly connected local tournament with exactly one non-separating vertex. In the first part of this paper we characterize the class of strongly connected local tournaments with exactly two non-separating vertices.In the second part of the paper we consider the following problem: Given a strongly connected local tournament D of order n with at least n+2 arcs and an integer 3≤r≤n. How many directed cycles of length r exist in D? For tournaments this problem was treated by Moon in 1966 and Las Vergnas in 1975. A reformulation of the results of the first part shows that we have characterized the class of strongly connected local tournaments with exactly two directed cycles of length n−1. Among other things we show that D has at least n−r+1 directed cycles of length r for 4≤r≤n−1 unless it has a special structure. Moreover, we characterize the class of local tournaments with exactly n−r+1 directed cycles of length r for 4≤r≤n−1 which generalizes a result of Las Vergnas.