Extremal digraphs avoiding distinct walks of length 3 with the same endpoints

In this paper, we determine the maximum size of digraphs on n vertices which avoid two distinct walks of length 3 with the same initial vertex and the same terminal vertex. The digraphs attaining this maximum size are also characterized. Combining this with previous results, we obtain a full solution to a problem proposed by X. Zhan in 2007.     

A Turán problem on digraphs avoiding distinct walks of a given length with the same endpoints

Let $k\ge 4$ and $n\ge k+4$ be positive integers. We determine the maximum size of digraphs of order $n$ that avoid distinct walks of length $k$ with the same endpoints. We also characterize the extremal digraphs attaining this maximum number when $k\ge 5$.     

Aparallel digraphs and splicing machines

The concepts of a splicing machine and of an aparalled digraph are introduced. A splicing machine is basically a means to uniquely obtain all circular sequences on a finite alphabet by splicing together circular sequences from a small finite set of “generators”. The existence and uniqueness of the central object related to an aparallel digraph, the strong component, is proved, and this strong component is shown to be the unique fixed point of a natural operator defined on sets of vertices of the digraph. A digraph is shown to be a splicing machine if and only if it is the strong component of an aparallel digraph. Motivation comes, on the applied side, from the splicing of circular sequences on a finite alphabet and, on the theoretical side, from the Banach fixed point theorem.     

Irregularity strength of digraphs

It is an elementary exercise to show that any non-trivial simple graph has two vertices with the same degree. This is not the case for digraphs and multigraphs. We consider generating irregular digraphs from arbitrary digraphs by adding multiple arcs. To this end, we define an irregular labeling of a digraph D to be an arc-labeling of the digraph such that the ordered pairs of the sums of the in-labels and out-labels at each vertex are all distinct. We define the strength of D to be the smallest of the maximum labels used across all irregular labelings. Similar definitions for graphs have been studied extensively and a different formulation of digraph irregularity was given in [H. Hackett, Irregularity strength of graphs and digraphs, Masters Thesis, University of Louisville, 1995]. Here we continue the study of irregular labelings of digraphs. We give a general lower bound on and determine exactly for tournaments, directed paths and cycles and the orientation of the path where all vertices have either in-degree 0 or out-degree 0. We also determine the irregularity strength of a union of directed cycles and a union of directed paths, the latter which requires a new result pertaining to finding circuits of given lengths containing prescribed vertices in the complete symmetric digraph with loops.     

Descendant-homogeneous digraphs

The descendant setdesc(α) of a vertex α in a digraph D is the set of vertices which can be reached by a directed path from α. A subdigraph of D is finitely generated if it is the union of finitely many descendant sets, and D is descendant-homogeneous if it is vertex transitive and any isomorphism between finitely generated subdigraphs extends to an automorphism. We consider connected descendant-homogeneous digraphs with finite out-valency, specially those which are also highly arc-transitive. We show that these digraphs must be imprimitive. In particular, we study those which can be mapped homomorphically onto Z and show that their descendant sets have only one end.There are examples of descendant-homogeneous digraphs whose descendant sets are rooted trees. We show that these are highly arc-transitive and do not admit a homomorphism onto Z. The first example (Evans (1997) [6]) known to the authors of a descendant-homogeneous digraph (which led us to formulate the definition) is of this type. We construct infinitely many other descendant-homogeneous digraphs, and also uncountably many digraphs whose descendant sets are rooted trees but which are descendant-homogeneous only in a weaker sense, and give a number of other examples.     

Recognizing digraphs of Kelly-width 2

Kelly-width is a parameter of digraphs recently proposed by Hunter and Kreutzer as a directed analogue of treewidth. We give an alternative characterization of digraphs of bounded Kelly-width in support of this analogy, and the first polynomial-time algorithm recognizing digraphs of Kelly-width 2. For an input digraph G=(V,A) the algorithm outputs a vertex ordering and a digraph H=(V,B) with A⊆B witnessing either that G has Kelly-width at most 2 or that G has Kelly-width at least 3, in time linear in H.     

3-Restricted arc connectivity of digraphs

The $k$-restricted arc connectivity of digraphs is a common generalization of the arc connectivity and the restricted arc connectivity. An arc subset $S$ of a strong digraph $D$ is a $k$-restricted arc cut if $D?S$ has a strong component $D^{\prime }$ with order at least $k$ such that $D?V\left(D^{\prime }\right)$ contains a connected subdigraph with order at least $k$. The $k$-restricted arc connectivity ${\lambda }^k\left(D\right)$ of a digraph $D$ is the minimum cardinality over all $k$-restricted arc cuts of $D$.Let $D$ be a strong digraph with order $n\ge 6$ and minimum degree $\delta \left(D\right)$. In this paper, we first show that ${\lambda }^3\left(D\right)$ exists if $\delta \left(D\right)\ge 3$ and, furthermore, ${\lambda }^3\left(D\right)\le {\xi }^3\left(D\right)$ if $\delta \left(D\right)\ge 4$, where ${\xi }^3\left(D\right)$ is the minimum 3-degree of $D$. Next, we prove that ${\lambda }^3\left(D\right)={\xi }^3\left(D\right)$ if $\delta \left(D\right)\ge \frac{n+3}{2}$. Finally, we give examples showing that these results are best possible in some sense.     

ON THE EXPONENT SET OF PRIMITIVELOCALLY SEMICOMPLETE DIGRAPHS

A locally semicomplete digraph is a digraph D=(V,A) satisfying the following condi-tion for every vertex x∈V the D[O(x)] and D[I(x)] are semicomplete digraphs. In this paper,we get some properties of cycles and determine the exponent set of primitive locally semicompleted digraphs.     

On detour homogeneous digraphs

If every vertex of a graph is an endvertex of a hamiltonian path, then the graph is called homogeneously traceable. If we require each vertex of a graph to be an endvertex of a longest path (not necessarily a hamiltonian path), then we call the graph a detour homogeneous graph. The concept of a homogeneously traceable graph was extended to digraphs by Bermond, Simões-Pereira, and C.M. Zamfirescu. Skupień introduced different classes of such digraphs. In this paper we discuss the extension of the concept of a detour homogeneous graph to digraphs.     

Distance and size in digraphs

We determine the maximum number of arcs in an Eulerian digraph of given order and diameter. Our bound generalises a classical result on the maximum number of edges of an undirected graph of given order and diameter by Ore (1968) and Homenko and Ostroverhii? (1970). We further determine the maximum size of a bipartite digraph of given order and radius.     

Kernels of digraphs with finitely many ends

According to Richardson’s theorem, every digraph $G$ without directed odd cycles that is either (a) locally finite or (b) rayless has a kernel (an independent subset $K$ with an incoming edge from every vertex in $G?K$). We generalize this theorem showing that a digraph without directed odd cycles has a kernel when (a) for each vertex, there is a finite set separating it from all rays, or (b) each ray contains at most finitely many vertices dominating it (having an infinite fan to the ray) and the digraph has finitely many ends. The restriction to finitely many ends in (b) can be weakened, admitting infinitely many ends with a specific structure, but the possibility of dropping it remains a conjecture.     

Improved upper and lower bounds for the spectral radius of digraphs

Let G be a digraph with n vertices and m arcs without loops and multiarcs. The spectral radius ρ(G) of G is the largest eigenvalue of its adjacency matrix. In this paper, sharp upper and lower bounds on ρ(G) are given. We show that some known bounds can be obtained from our bounds.     

Bartholdi zeta functions of digraphs

We give a determinant expression for the Bartholdi zeta function of a digraph which is not symmetric. This is a generalization of Bartholdi’s result on the Bartholdi zeta function of a graph or a symmetric digraph.     

Characterizations of Clifford semigroup digraphs

This paper characterizes directed graphs which are Cayley graphs of strong semilattices of groups and, in particular, strong chains of groups, i.e. of completely regular semigroups which are also called Clifford semigroups.     

Bounded degree acyclic decompositions of digraphs

An acyclic decomposition of a digraph is a partition of the edges into acyclic subgraphs. Trivially every digraph has an acyclic decomposition into two subgraphs. It is proved that for every integer s2 every digraph has an acyclic decomposition into s subgraphs such that in each subgraph the outdegree of each vertex v is at most . For all digraphs this degree bound is optimal.     

Some approaches to a conjecture on short cycles in digraphs

We consider the following special case of a conjecture due to Caccetta and Häggkvist: Let D be a digraph on n vertices that all have in-degree and out-degree at least n/3. Then, D contains a directed cycle of length 2 or 3. We discuss several necessary conditions for possible counterexamples to this conjecture, in terms of cycle structure, diameter, maximum degree, clique number, toughness, and local structure. These conditions have not enabled us to prove or refute the conjecture, but they lead to proofs of special instances of the conjecture.     

Cyclic matrices of weighted digraphs

In this paper, we address several properties of the so-called augmented cyclic matrices of weighted digraphs. These matrices arise in different applications of digraph theory to electrical circuit analysis, and can be seen as an enlargement of basic cyclic matrices of the form BWB^T, where B is a cycle matrix and W is a diagonal matrix of weights. By using certain matrix factorizations and some properties of cycle bases, we characterize the determinant of augmented cyclic matrices, via Cauchy-Binet expansions, in terms of the so-called proper cotrees. In the simpler context defined by basic cyclic matrices, we obtain the dual result of Maxwell’s determinantal expansion for weighted Laplacian (nodal) matrices. Additional relations with nodal matrices are also discussed. We apply this framework to the characterization of the differential-algebraic circuit models arising from loop analysis, and also to the analysis of branch-oriented models of circuits including charge-controlled memristors.