Maximum Directed Cuts in Graphs with Degree Constraints

The Max Cut problem is an NP-hard problem and has been studied extensively. Alon et?al. (J Graph Theory 55:1–13, 2007) studied a directed version of the Max Cut problem and observed its connection to the Hall ratio of graphs. They proved, among others, that if an acyclic digraph has m edges and each vertex has indegree or outdegree at most 1, then it has a directed cut of size at least 2m/5. Lehel et?al. (J Graph Theory 61:140–156, 2009) extended this result by replacing the “acyclic digraphs” with the “digraphs containing no directed triangles”. In this paper, we characterize the acyclic digraphs with m edges whose maximum dicuts have exactly 2m/5 edges, and our approach gives an alternative proof of the result of Lehel et?al. We also show that there are infinitely many positive rational numbers β < 2/5 for which there exist digraphs D (with directed triangles) such that each vertex of D has indegree or outdegree at most 1, and any maximum directed cut in D has size precisely β|E(D)|.     

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.     

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.     

Multipartite Moore digraphs

We derive some Moore-like bounds for multipartite digraphs, which extend those of bipartite digraphs, under the assumption that every vertex of a given partite set is adjacent to the same number δ of vertices in each of the other independent sets. We determine when a multipartite Moore digraph is weakly distance-regular. Within this framework, some necessary conditions for the existence of a r-partite Moore digraph with interpartite outdegree δ > 1 and diameter k = 2m are obtained. In the case δ = 1, which corresponds to almost Moore digraphs, a necessary condition in terms of the permutation cycle structure is derived. Additionally, we present some constructions of dense multipartite digraphs of diameter two that are vertex-transitive.     

Efficient total domination in digraphs

We generalize the concept of efficient total domination from graphs to digraphs. An efficiently total dominating set X of a digraph D is a vertex subset such that every vertex of D has exactly one predecessor in X. We study graphs that permit an orientation having such a set and give complexity results and characterizations. Furthermore, we study the computational complexity of the (weighted) efficient total domination problem for several digraph classes. In particular we deal with most of the common generalizations of tournaments, like locally semicomplete and arc-locally semicomplete digraphs.     

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.     

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.     

Independent sets and non-augmentable paths in arc-locally in-semicomplete digraphs and quasi-arc-transitive digraphs

A digraph is arc-locally in-semicomplete if for any pair of adjacent vertices x,y, every in-neighbor of x and every in-neighbor of y either are adjacent or are the same vertex. A digraph is quasi-arc-transitive if for any arc xy, every in-neighbor of x and every out-neighbor of y either are adjacent or are the same vertex. Laborde, Payan and Xuong proposed the following conjecture: Every digraph has an independent set intersecting every non-augmentable path (in particular, every longest path). In this paper, we shall prove that this conjecture is true for arc-locally in-semicomplete digraphs and quasi-arc-transitive digraphs.     

Kernels and some operations in edge-coloured digraphs

Let D be an edge-coloured digraph, V(D) will denote the set of vertices of D; a set N⊆V(D) is said to be a kernel by monochromatic paths of D if it satisfies the following two conditions: For every pair of different vertices u,v∈N there is no monochromatic directed path between them and; for every vertex x∈V(D)−N there is a vertex y∈N such that there is an xy-monochromatic directed path.In this paper we consider some operations on edge-coloured digraphs, and some sufficient conditions for the existence or uniqueness of kernels by monochromatic paths of edge-coloured digraphs formed by these operations from another edge-coloured digraphs.     

Multiplicativity of acyclic local tournaments

A homomorphism of a digraph to another digraph is an edge-preserving vertex mapping. A digraphH is said to be multiplicative if the set of digraphs which do not admit a homomorphism toH is closed under categorical product. In this paper we discuss the multiplicativity of acyclic Hamiltonian digraphs, i.e., acyclic digraphs which contains a Hamiltonian path. As a consequence, we give a complete characterization of acyclic local tournaments with respect to multiplicativity.     

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.     

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.     

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

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

An algorithm for finding hamilton cycles in random directed graphs

We describe a polynomial (O(n^1.5)) time algorithm DHAM for finding hamilton cycles in digraphs. For digraphs chosen uniformly at random from the set of digraphs with vertex set {1, 2, …, n} and m = m(n) edges the limiting probability (as n → ∞) that DHAM finds a hamilton cycle equals the limiting probability that the digraph is hamiltonian. Some applications to random “travelling salesman problems” are discussed.     

Switching Reconstruction of Digraphs

Switching about a vertex in a digraph means to reverse the direction of every edge incident with that vertex. Bondy and Mercier introduced the problem of whether a digraph can be reconstructed up to isomorphism from the multiset of isomorphism types of digraphs obtained by switching about each vertex. Since the largest known nonreconstructible oriented graphs have eight vertices, it is natural to ask whether there are any larger nonreconstructible graphs. In this article, we continue the investigation of this question. We find that there are exactly 44 nonreconstructible oriented graphs whose underlying undirected graphs have maximum degree at most 2. We also determine the full set of switching‐stable oriented graphs, which are those graphs for which all switchings return a digraph isomorphic to the original.     

Characterizing Extremal Digraphs for Identifying Codes and Extremal Cases of Bondy’s Theorem on Induced Subsets

An identifying code of a (di)graph G is a dominating subset C of the vertices of G such that all distinct vertices of G have distinct (in)neighbourhoods within C. In this paper, we classify all finite digraphs which only admit their whole vertex set as an identifying code. We also classify all such infinite oriented graphs. Furthermore, by relating this concept to a well-known theorem of Bondy on set systems, we classify the extremal cases for this theorem.     

Arc‐Disjoint In‐ and Out‐Branchings With the Same Root in Locally Semicomplete Digraphs

Deciding whether a digraph contains a pair of arc‐disjoint in‐ and out‐branchings rooted at a specified vertex is a well‐known NP‐complete problem (as proved by Thomassen, see 2 ). This problem has been shown to be polynomial time solvable for semicomplete digraphs 2 and for quasi‐transitive digraphs 6 . In this article, we study the problem for locally semicomplete digraphs. We characterize locally semicomplete digraphs that contain a pair of arc‐disjoint in‐ and out‐branchings rooted at a specified vertex. Our proofs are constructive and imply the existence of a polynomial time algorithm for finding the desired branchings when they exist. Our results generalizes those from 2 for semicomplete digraphs and solves an open problem from 4 .     

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.     

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.