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     

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     

The complexity of colouring by locally semicomplete digraphs

In this paper we establish a dichotomy theorem for the complexity of homomorphisms to fixed locally semicomplete digraphs. It is also shown that the same dichotomy holds for list homomorphisms. The polynomial algorithms follow from a different, shorter proof of a result by Gutjahr, Welzl and Woeginger.     

On semicomplete multipartite digraphs whose king sets are semicomplete digraphs

Reid [Every vertex a king, Discrete Math. 38 (1982) 93-98] showed that a non-trivial tournament H is contained in a tournament whose 2-kings are exactly the vertices of H if and only if H contains no transmitter. Let T be a semicomplete multipartite digraph with no transmitters and let K_r(T) denote the set of r-kings of T. Let Q be the subdigraph of T induced by K₄(T). Very recently, Tan [On the kings and kings-of-kings in semicomplete multipartite digraphs, Discrete Math. 290 (2005) 249-258] proved that Q contains no transmitters and gave an example to show that the direct extension of Reid's result to semicomplete multipartite digraphs with 2-kings replaced by 4-kings is not true. In this paper, we (1) characterize all semicomplete digraphs D which are contained in a semicomplete multipartite digraph whose 4-kings are exactly the vertices of D. While it is trivial that K₄(Q)⊆K₄(T), Tan [On the kings and kings-of-kings in semicomplete multipartite digraphs, Discrete Math. 290 (2005) 249-258] showed that K₃(Q)⊆K₃(T) and K₂(Q)=K₂(T). Tan [On the kings and kings-of-kings in semicomplete multipartite digraphs, Discrete Math. 290 (2005) 249-258] also provided an example to show that K₃(Q) need not be the same as K₃(T) in general and posed the problem: characterize all those semicomplete multipartite digraphs T such that K₃(Q)=K₃(T). In the course of proving our result (1), we (2) show that K₃(Q)=K₃(T) for all semicomplete multipartite digraphs T with no transmitters such that Q is a semicomplete digraph.     

Finding cheapest cycles in vertex-weighted quasi-transitive and extended semicomplete digraphs

We consider the problem of finding a minimum cost cycle in a digraph with real-valued costs on the vertices. This problem generalizes the problem of finding a longest cycle and hence is NP-hard for general digraphs. We prove that the problem is solvable in polynomial time for extended semicomplete digraphs and for quasi-transitive digraphs, thereby generalizing a number of previous results on these classes. As a byproduct of our method we develop polynomial algorithms for the following problem: Given a quasi-transitive digraph D with real-valued vertex costs, find, for each j=1,2,…,|V(D)|, j disjoint paths P₁,P₂,…,P_j such that the total cost of these paths is minimum among all collections of j disjoint paths in D.     

Minimum cost homomorphisms to semicomplete multipartite digraphs

For digraphs D and H, a mapping f:V(D)→V(H) is a homomorphism ofDtoH if uv∈A(D) implies f(u)f(v)∈A(H). For a fixed directed or undirected graph H and an input graph D, the problem of verifying whether there exists a homomorphism of D to H has been studied in a large number of papers. We study an optimization version of this decision problem. Our optimization problem is motivated by a real-world problem in defence logistics and was introduced recently by the authors and M. Tso.Suppose we are given a pair of digraphs D,H and a cost c_i(u) for each u∈V(D) and i∈V(H). The cost of a homomorphism f of D to H is ∑_u∈V(D)c_f(u)(u). Let H be a fixed digraph. The minimum cost homomorphism problem for H, MinHOMP(H), is stated as follows: For input digraph D and costs c_i(u) for each u∈V(D) and i∈V(H), verify whether there is a homomorphism of D to H and, if it does exist, find such a homomorphism of minimum cost. In our previous paper we obtained a dichotomy classification of the time complexity of when H is a semicomplete digraph. In this paper we extend the classification to semicomplete k-partite digraphs, k≥3, and obtain such a classification for bipartite tournaments.     

Minimum cost and list homomorphisms to semicomplete digraphs

For digraphs D and H, a mapping f:V(D)→V(H) is a homomorphism of D to H if uv∈A(D) implies f(u)f(v)∈A(H). Let H be a fixed directed or undirected graph. The homomorphism problem for H asks whether a directed or undirected input graph D admits a homomorphism to H. The list homomorphism problem for H is a generalization of the homomorphism problem for H, where every vertex x∈V(D) is assigned a set L_x of possible colors (vertices of H).The following optimization version of these decision problems generalizes the list homomorphism problem and was introduced in Gutin et al. [Level of repair analysis and minimum cost homomorphisms of graphs, Discrete Appl. Math., to appear], where it was motivated by a real-world problem in defence logistics. Suppose we are given a pair of digraphs D,H and a positive integral cost c_i(u) for each u∈V(D) and i∈V(H). The cost of a homomorphism f of D to H is . For a fixed digraph H, the minimum cost homomorphism problem for H is stated as follows: for an input digraph D and costs c_i(u) for each u∈V(D) and i∈V(H), verify whether there is a homomorphism of D to H and, if one exists, find such a homomorphism of minimum cost.We obtain dichotomy classifications of the computational complexity of the list homomorphism and minimum cost homomorphism problems, when H is a semicomplete digraph (digraph in which there is at least one arc between any two vertices). Our dichotomy for the list homomorphism problem coincides with the one obtained by Bang-Jensen, Hell and MacGillivray in 1988 for the homomorphism problem when H is a semicomplete digraph: both problems are polynomial solvable if H has at most one cycle; otherwise, both problems are NP-complete. The dichotomy for the minimum cost homomorphism problem is different: the problem is polynomial time solvable if H is acyclic or H is a cycle of length 2 or 3; otherwise, the problem is NP-hard.     

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.     

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.     

A polynomial algorithm for the Hamiltonian cycle problem in semicomplete multipartite digraphs

We describe a polynomial algorithm for the Hamiltonian cycle problem for semicomplete multipartite digraphs. The existence of such an algorithm was conjectured in G. Gutin, Paths and cycles in digraphs. Ph. D. thesis, Tel Aviv Univ., 1993. (see also G. Gutin, J Graph Theory 19 (1995) 481–505). © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 111–132, 1998     

The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops

For digraphs D and H, a mapping f:V(D)→V(H) is a homomorphism of D to H if uv∈A(D) implies f(u)f(v)∈A(H). For a fixed digraph H, the homomorphism problem is to decide whether an input digraph D admits a homomorphism to H or not, and is denoted as HOM(H).An optimization version of the homomorphism problem was motivated by a real-world problem in defence logistics and was introduced in Gutin, Rafiey, Yeo and Tso (2006) [13]. If each vertex u∈V(D) is associated with costs c_i(u),i∈V(H), then the cost of the homomorphism f is ∑_u∈V(D)c_f(u)(u). For each fixed digraph H, we have the minimum cost homomorphism problem forH and denote it as MinHOM(H). The problem is to decide, for an input graph D with costs c_i(u),u∈V(D),i∈V(H), whether there exists a homomorphism of D to H and, if one exists, to find one of minimum cost.Although a complete dichotomy classification of the complexity of MinHOM(H) for a digraph H remains an unsolved problem, complete dichotomy classifications for MinHOM(H) were proved when H is a semicomplete digraph Gutin, Rafiey and Yeo (2006) [10], and a semicomplete multipartite digraph Gutin, Rafiey and Yeo (2008) [12] and [11]. In these studies, it is assumed that the digraph H is loopless. In this paper, we present a full dichotomy classification for semicomplete digraphs with possible loops, which solves a problem in Gutin and Kim (2008) [9].     

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.     

Blaschke structure for a special affine immersion

In this paper we determine a Blaschke structure for affine immersion of Euclidian and Hyperbolic type for plane equi-affine curve. In particular, we consider this structure in the case where the Ricci tensor of affine immersion is constant and give a necessary and sufficient condition for Ricci tensor to be constant.     

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.     

Degree sequence conditions for maximally edge-connected and super-edge-connected digraphs depending on the clique number

Let $D$ be a finite and simple digraph with vertex set $V\left(D\right)$. For a vertex $v\in V\left(D\right)$, the degree $d\left(v\right)$ of $v$ is defined as the minimum value of its out-degree $d^{+}\left(v\right)$ and its in-degree $d^{?}\left(v\right)$. If $D$ is a graph or a digraph with minimum degree $\delta$ and edge-connectivity $\lambda$, then $\lambda \le \delta$. A graph or a digraph is maximally edge-connected if $\lambda =\delta$. A graph or a digraph is called super-edge-connected if every minimum edge-cut consists of edges adjacent to or from a vertex of minimum degree.In this note we present degree sequence conditions for maximally edge-connected and super-edge-connected digraphs depending on the clique number of the underlying graph.     

Disjoint paths in symmetric digraphs

Given a number of requests ?, we propose a polynomial-time algorithm for finding ? disjoint paths in a symmetric directed graph. It is known that the problem of finding ?≥2 disjoint paths in a directed graph is NP-hard [S. Fortune, J. Hopcroft, J. Wyllie, The directed subgraph homeomorphism problem, Journal of Theoretical Computer Science 10 (2) (1980) 111-121]. However, by studying minimal solutions it turns out that only a finite number of configurations are possible in a symmetric digraph. We use Robertson and Seymour’s polynomial-time algorithm [N. Robertson, P. D. Seymour, Graph minors xiii. The disjoint paths problem, Journal of Combinatorial Theory B (63) (1995) 65-110] to check the feasibility of each configuration.     

Reinforcement numbers of digraphs

The reinforcement number of a graph G is the minimum cardinality of a set of extra edges whose addition results in a graph with domination number less than the domination number of G. In this paper we consider this parameter for digraphs, investigate the relationship between reinforcement numbers of undirected graphs and digraphs, and obtain further results for regular graphs. We also determine the exact values of the reinforcement numbers of de Bruijn digraphs and Kautz digraphs.