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 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.     

Disjoint quasi‐kernels in digraphs

A quasi‐kernel in a digraph is an independent set of vertices such that any vertex in the digraph can reach some vertex in the set via a directed path of length at most two. Chvátal and Lovász proved that every digraph has a quasi‐kernel. Recently, Gutin et al. raised the question of which digraphs have a pair of disjoint quasi‐kernels. Clearly, a digraph has a pair of disjoint quasi‐kernels cannot contain sinks, that is, vertices of outdegree zero, as each such vertex is necessarily included in a quasi‐kernel. However, there exist digraphs which contain neither sinks nor a pair of disjoint quasi‐kernels. Thus, containing no sinks is not sufficient in general for a digraph to have a pair of disjoint quasi‐kernels. In contrast, we prove that, for several classes of digraphs, the condition of containing no sinks guarantees the existence of a pair of disjoint quasi‐kernels. The classes contain semicomplete multipartite, quasi‐transitive, and locally semicomplete digraphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:251‐260, 2008     

Kings in locally semicomplete digraphs

A k‐king in a digraph D is a vertex which can reach every other vertex by a directed path of length at most k. We consider k‐kings in locally semicomplete digraphs and mainly prove that all strong locally semicomplete digraphs which are not round decomposable contain a 2‐king. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 279–287, 2010     

The structure of strong arc-locally in-semicomplete 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. In this paper, we study the structure of strong arc-locally in-semicomplete digraphs and prove that a strong arc-locally in-semicomplete digraph is either arc-locally semicomplete or in a special class of digraphs. Using this structural characterization, we show that a 2-strong arc-locally in-semicomplete digraph is arc-locally semicomplete and a conjecture of Bang-Jensen is true.     

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.     

Cycles and paths in semicomplete multipartite digraphs,theorems, and algorithms: a survey

A digraph obtained by replacing each edge of a complete m-partite graph by an arc or a pair of mutually opposite arcs with the same end vertices is calied a semicomplete m-partite digraph. We describe results (theorems and algorithms) on directed walks in semicomplete m-partite digraphs, including some recent results concerning tournaments. © 1995 John Wiley & Sons, Inc.     

One-diregular subgraphs in semicomplete multipartite digraphs

The problem of finding necessary and sufficient conditions for a semicomplete multipartite digraph (SMD) to be Hamiltonian, seems to be both very interesting and difficult. Bang-Jensen, Gutin and Huang ( Discrete Math to appear) proved a sufficient condition for a SMD to be Hamiltonian. A strengthening of this condition, shown in this paper, allows us to prove the following three results. We prove that every k-strong SMD with at most k-vertices in each color class is Hamiltonian and every k-strong SMD has a cycle through any set of k vertices. These two statements were stated as conjectures by Volkmann (L. Volkmann, a talk at the second Krakw Conference of Graph Theory (1994)) and Bang-Jensen, Gutin, and Yeo (J. Bang-Jensen, G. Gutin, and A. Yeo, On k-strong and k-cyclic digraphs, submitted), respectively. We also prove that every diregular SMD is Hamiltonian, which was conjectured in a weaker form by Zhang (C.-Q. Zhang, Hamilton paths in multipartite oriented graphs, Ann Discrete Math. 41 (1989), 499–581). © 1997 John Wiley & Sons, Inc.     

A class of self-complementary vertex-transitive digraphs

We characterize the class of self-complementary vertex-transitive digraphs on a prime number p of vertices. Using this, we enumerate (i) self-complementary strongly vertex-transitive digraphs on p vertices, (ii) self-complementary vertex-transitive digraphs on p vertices, (iii) self-complementary vertex-transitive graphs on p vertices. Finally it is shown that every self-complementary vertex-transitive digraph on p vertices is either a tournament or a graph.     

Kings in semicomplete multipartite digraphs

A digraph obtained by replacing each edge of a complete p‐partite graph by an arc or a pair of mutually opposite arcs with the same end vertices is called a semicomplete p‐partite digraph, or just a semicomplete multipartite digraph. A semicomplete multipartite digraph with no cycle of length two is a multipartite tournament. In a digraph D, an r‐king is a vertex q such that every vertex in D can be reached from q by a path of length at most r. Strengthening a theorem by K. M. Koh and B. P. Tan (Discr Math 147 (1995), 171–183) on the number of 4‐kings in multipartite tournaments, we characterize semicomplete multipartite digraphs, which have exactly k 4‐kings for every k = 1, 2, 3, 4, 5. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 177‐183, 2000     

Almost Minimum Diameter Orientations of Semicomplete Multipartite and Extended Digraphs

 An orientation of a digraph D is a spanning subdigraph of D obtained from D by deleting exactly one arc between x and y for every pair x≠y of vertices such that both x y and y x are in D. Almost minimum diameter orientations of certain semicomplete multipartite and extended digraphs are considered, several generalizations of results on orientations of undirected graphs are obtained, some conjectures are posed. Received: August 31, 2000 Final version received: October 30, 2001 Acknowledgments. Part of this work was done when the first author was visiting the Department of Mathematics, National University of Singapore. The departmental hospitality and financial support are very much appreciated.     

Spanning 2-strong tournaments in 3-strong semicomplete digraphs

We prove that every 3-strong semicomplete digraph on at least 5 vertices contains a spanning 2-strong tournament. Our proof is constructive and implies a polynomial algorithm for finding a spanning 2-strong tournament in a given 3-strong semicomplete digraph. We also show that there are infinitely many (2k−2)-strong semicomplete digraphs which contain no spanning k-strong tournament and conjecture that every(2k−1)-strong semicomplete digraph which is not the complete digraph on 2k vertices contains a spanning k-strong tournament.     

On the structure of strong 3-quasi-transitive digraphs

In this paper, D=(V(D),A(D)) denotes a loopless directed graph (digraph) with at most one arc from u to v for every pair of vertices u and v of V(D). Given a digraph D, we say that D is 3-quasi-transitive if, whenever u→v→w→z in D, then u and z are adjacent or u=z. In Bang-Jensen (2004) [3], Bang-Jensen introduced 3-quasi-transitive digraphs and claimed that the only strong 3-quasi-transitive digraphs are the strong semicomplete digraphs and strong semicomplete bipartite digraphs. In this paper, we exhibit a family of strong 3-quasi-transitive digraphs distinct from strong semicomplete digraphs and strong semicomplete bipartite digraphs and provide a complete characterization of strong 3-quasi-transitive digraphs.     

On the structure of locally semicomplete digraphs

In this paper we continue the study, started by J. Bang-Jensen (1989), of locally semicomplete digraphs, a generalization of tournaments, to which many well-known tournament results extend. The underlying undirected graphs of the locally semicomplete digraphs are precisely the proper circular-arc graphs. We give new results on the structure of locally semicomplete digraphs, as well as several examples of properties of tournaments and semicomplete digraphs that do not extend to the class of locally semicomplete digraphs.     

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.     

Maximum diameter of regular digraphs

We prove that every r-biregular digraph with n vertices has its directed diamter bounded by (3n - r - 3)/(r +1). We show that this bound is tight for directed as well as for undirected graphs. The upper bound remains valid for Eulerian digraphs with minimum outdegree r. © 1929 John Wiley & Sons, Inc.     

A well-quasi-order for tournaments

A digraph H is immersed in a digraph G if the vertices of H are mapped to (distinct) vertices of G, and the edges of H are mapped to directed paths joining the corresponding pairs of vertices of G, in such a way that the paths are pairwise edge-disjoint. For graphs the same relation (using paths instead of directed paths) is a well-quasi-order; that is, in every infinite set of graphs some one of them is immersed in some other. The same is not true for digraphs in general; but we show it is true for tournaments (a tournament is a directed complete graph).     

Strongly Hamiltonian-connected locally semicomplete digraphs

We give some sufficient conditions for locally semicomplete digraphs to contain a hamiltonian path from a prescribed vertex to another prescribed vertex. As an immediate consequence of these, we obtain that every 4-connected locally semicomplete digraph is strongly hamiltonian-connected. Our results extend those of Thomassen [12] for tournaments. © 1996 John Wiley & Sons, Inc.     

Digraphs with the path-merging property

In this paper we study those digraphs D for which every pair of internally disjoint (X, Y)-paths P₁, P₂ can be merged into one (X, Y)-path P* such that V(P₁) ∪ V(P₂), for every choice of vertices X, Y ? V(D). We call this property the path-merging property and we call a graph path-mergeable if it has the path-merging property. We show that each such digraph has a directed hamiltonian cycle whenever it can possibly have one, i.e., it is strong and the underlying graph has no cutvertex. We show that path-mergeable digraphs can be recognized in polynomial time and we give examples of large classes of such digraphs which are not contained in any previously studied class of digraphs. We also discuss which undirected graphs have path-mergeable digraph orientations. © 1995, John Wiley & Sons, Inc.     

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.