Completing orientations of partially oriented graphs

We initiate a general study of what we call orientation completion problems. For a fixed class of oriented graphs, the orientation completion problem asks whether a given partially oriented graph P can be completed to an oriented graph in by orienting the (nonoriented) edges in P. Orientation completion problems commonly generalize several existing problems including recognition of certain classes of graphs and digraphs as well as extending representations of certain geometrically representable graphs. We study orientation completion problems for various classes of oriented graphs, including k‐arc‐strong oriented graphs, k‐strong oriented graphs, quasi‐transitive‐oriented graphs, local tournaments, acyclic local tournaments, locally transitive tournaments, locally transitive local tournaments, in‐tournaments, and oriented graphs that have directed cycle factors. We show that the orientation completion problem for each of these classes is either polynomial time solvable or NP‐complete. We also show that some of the NP‐complete problems become polynomial time solvable when the input‐oriented graphs satisfy certain extra conditions. Our results imply that the representation extension problems for proper interval graphs and for proper circular arc graphs are polynomial time solvable. The latter generalizes a previous result.     

Oriented bipartite graphs and the Goldbach graph

In this paper, we study oriented bipartite graphs. In particular, we introduce “bitransitive” graphs. Several characterizations of bitransitive bitournaments are obtained. We show that bitransitive bitounaments are equivalent to acyclic bitournaments. As applications, we characterize acyclic bitournaments with Hamiltonian paths, determine the number of non-isomorphic acyclic bitournaments of a given order, and solve the graph-isomorphism problem in linear time for acyclic bitournaments. Next, we prove the well-known Caccetta-Häggkvist Conjecture for oriented bipartite graphs in some cases for which it is unsolved, in general, for oriented graphs. We also introduce the concept of undirected as well as oriented “odd-even” graphs. We characterize bipartite graphs and acyclic oriented bipartite graphs in terms of them. In fact, we show that any bipartite graph (acyclic oriented bipartite graph) can be represented by some odd-even graph (oriented odd-even graph). We obtain some conditions for connectedness of odd-even graphs. This study of odd-even graphs and their connectedness is motivated by a special family of odd-even graphs which we call “Goldbach graphs”. We show that the famous Goldbach's conjecture is equivalent to the connectedness of Goldbach graphs. Several other number theoretic conjectures (e.g., the twin prime conjecture) are related to various parameters of Goldbach graphs, motivating us to study the nature of vertex-degrees and independent sets of these graphs. Finally, we observe Hamiltonian properties of some odd-even graphs related to Goldbach graphs for a small number of vertices.     

The Second Neighbourhood for Quasi-transitive Oriented Graphs

In 2006, Sullivan stated the conjectures:(1) every oriented graph has a vertex x such that d~(++)(x) ≥ d~-(x);(2) every oriented graph has a vertex x such that d~(++)(x) + d~+(x) ≥ 2 d~-(x);(3) every oriented graph has a vertex x such that d~(++)(x) + d~+(x) ≥ 2 · min{d~+(x), d~-(x)}. A vertex x in D satisfying Conjecture(i) is called a Sullivan-i vertex, i = 1, 2, 3. A digraph D is called quasi-transitive if for every pair xy, yz of arcs between distinct vertices x, y, z, xz or zx("or" is inclusive here) is in D. In this paper, we prove that the conjectures hold for quasi-transitive oriented graphs, which is a superclass of tournaments and transitive acyclic digraphs. Furthermore, we show that a quasi-transitive oriented graph with no vertex of in-degree zero has at least three Sullivan-1 vertices and a quasi-transitive oriented graph has at least three Sullivan-3 vertices unless it belongs to an exceptional class of quasitransitive oriented graphs. For Sullivan-2 vertices, we show that an extended tournament, a subclass of quasi-transitive oriented graphs and a superclass of tournaments, has at least two Sullivan-2 vertices unless it belongs to an exceptional class of extended tournaments.     

Partitions and orientations of the Rado graph

We classify the countably infinite oriented graphs which, for every partition of their vertex set into two parts, induce an isomorphic copy of themselves on at least one of the parts. These graphs are the edgeless graph, the random tournament, the transitive tournaments of order type  , and two orientations of the Rado graph: the random oriented graph, and a newly found random acyclic oriented graph.

     

On homomorphisms to acyclic local tournaments

A homomorphism of a digraph to another digraph is an edgepreserving vertex mapping. A local tournament is a digraph in which the inset as well as the outset of each vertex induces a tournament. Thus acyclic local tournaments generalize both directed paths and transitive tournaments. In both these cases there is a simple characterization of homomorphic preimages. Namely, if H is a directed path, or a transitive tournament, then G admits a homomorphism to H if and only if each oriented path which admits a homomorphism to G also admits a homomorphism to H. We prove that this result holds for all acyclic local tournaments. © 1995 John Wiley & Sons, Inc.     

完全多部图的区间图完全化问题

The interval graph completion problem of a graph G includes two class problems: the profile problem and the pathwidth problem, denoted as P(G) and PW(G) respectively, where the profile problem is to find an interval supergraph with the smallest possible number of edges; the pathwidth problem is to find an interval supergraph with the smallest possible cliquesize. These two class problems have important applications to numerical algebra, VLSI-layout and algorithm graph theory respectively; And they are known to be NP-complete for general graphs. Some classes of special graphs have been investigated in the literatures. In this paper the exact solutions of the profile and the pathwidth of the complete multipartite Graph Kn1,n2,…,nr(r≥2) are determined.     

Recognizing and representing proper interval graphs in parallel using merging and sorting

We present a parallel algorithm for recognizing and representing a proper interval graph in time with O(m+n) processors on the CREW PRAM, where m and n are the number of edges and vertices in the graph. The algorithm uses sorting to compute a weak linear ordering of the vertices, from which an interval representation is easily obtained. It is simple, uses no complex data structures, and extends ideas from an optimal sequential algorithm for recognizing and representing a proper interval graph [X. Deng, P. Hell, J. Huang, Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs, SIAM J. Comput. 25 (2) (1996) 390-403].     

Proper interval graphs and the guard problem

This paper is a study of the hamiltonicity of proper interval graphs with applications to the guard problem in spiral polygons. We prove that proper interval graphs with 2 vertices have hamiltonian paths, those with 3 vertices have hamiltonian cycles, and those with 4 vertices are hamiltonian-connected if and only if they are, respectively, 1-, 2-, or 3-connected. We also study the guard problem in spiral polygons by connecting the class of nontrivial connected proper interval graphs with the class of stick-intersection graphs of spiral polygons.     

An approximation result for the interval coloring problem on claw-free chordal graphs

We study the problem of finding an acyclic orientation of an undirected graph, such that each (oriented) path is covered by a limited number k of maximal cliques. This is equivalent to finding a k-approximate solution for the interval coloring problem on a graph. We focus our attention on claw-free chordal graphs, and show how to find an orientation of such a graph in linear time, which guarantees that each path is covered by at most two maximal cliques. This extends previous published results on other graph classes where stronger assumptions were made.     

Partial Characterizations of 1‐Perfectly Orientable Graphs

We study the class of 1‐perfectly orientable graphs, that is, graphs having an orientation in which every out‐neighborhood induces a tournament. 1‐perfectly orientable graphs form a common generalization of chordal graphs and circular arc graphs. Even though they can be recognized in polynomial time, little is known about their structure. In this article, we develop several results on 1‐perfectly orientable graphs. In particular, we (i) give a characterization of 1‐perfectly orientable graphs in terms of edge clique covers, (ii) identify several graph transformations preserving the class of 1‐perfectly orientable graphs, (iii) exhibit an infinite family of minimal forbidden induced minors for the class of 1‐perfectly orientable graphs, and (iv) characterize the class of 1‐perfectly orientable graphs within the classes of cographs and of cobipartite graphs. The class of 1‐perfectly orientable cobipartite graphs coincides with the class of cobipartite circular arc graphs.     

Acyclic improper colouring of graphs with maximum degree 4

A k-colouring(not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colours i and j the subgraph induced by the edges whose endpoints have colours i and j is acyclic. We consider acyclic k-colourings such that each colour class induces a graph with a given(hereditary) property. In particular, we consider acyclic k-colourings in which each colour class induces a graph with maximum degree at most t, which are referred to as acyclic t-improper k-colourings. The acyclic t-improper chromatic number of a graph G is the smallest k for which there exists an acyclic t-improper k-colouring of G. We focus on acyclic colourings of graphs with maximum degree 4. We prove that 3 is an upper bound for the acyclic 3-improper chromatic number of this class of graphs. We also provide a non-trivial family of graphs with maximum degree4 whose acyclic 3-improper chromatic number is at most 2, namely, the graphs with maximum average degree at most 3. Finally, we prove that any graph G with Δ(G) 4 can be acyclically coloured with 4 colours in such a way that each colour class induces an acyclic graph with maximum degree at most 3.     

A characterization of partial directed line graphs

Can a directed graph be completed to a directed line graph? If possible, how many arcs must be added? In this paper we address the above questions characterizing partial directed line (PDL) graphs, i.e., partial subgraph of directed line graphs. We show that for such class of graphs a forbidden configuration criterion and a Krausz's like theorem are equivalent characterizations. Furthermore, the latter leads to a recognition algorithm that requires O(m) worst case time, where m is the number of arcs in the graph. Given a partial line digraph, our characterization allows us to find a minimum completion to a directed line graph within the same time bound.The class of PDL graphs properly contains the class of directed line graphs, characterized in [J. Blazewicz, A. Hertz, D. Kobler, D. de Werra, On some properties of DNA graphs, Discrete Appl. Math. 98(1-2) (1999) 1-19], hence our results generalize those already known for directed line graphs. In the undirected case, we show that finding a minimum line graph edge completion is NP-hard, while the problem of deciding whether or not an undirected graph is a partial graph of a simple line graph is trivial.     

On arc-traceable local tournaments

A digraph D is arc-traceable if for every arc xy of D, the arc xy belongs to a directed Hamiltonian path of D. A local tournament is an oriented graph such that the negative neighborhood as well as the positive neighborhood of every vertex induces a tournament. It is well known that every tournament contains a directed Hamiltonian path and, in 1990, Bang-Jensen showed the same for connected local tournaments. In 2006, Busch, Jacobson and Reid studied the structure of tournaments that are not arc-traceable and consequently gave various sufficient conditions for tournaments to be arc-traceable. Inspired by the article of Busch, Jacobson and Reid, we develop in this paper the structure necessary for a local tournament to be not arc-traceable. Using this structure, we give sufficient conditions for a local tournament to be arc-traceable and we present examples showing that these conditions are best possible.     

A new lower bound on the strong connectivity of an oriented graph. Application to diameters with a particular case related to Caccetta Häggkvist conjecture

In this paper, by using minimum out-degree and minimum in-degree, we give a new lower bound on the vertex-strong connectivity of an oriented graph. In the case of a tournament, our lower bound improves that of Thomassen obtained in 1980 and which use the notion of irregularity (see [C. Thomassen, Hamiltonian-connected tournaments, J. Combin. Theory Ser. B 28 (1980) 142–163]). As application, we determine a pertinent upper bound on the diameter of some oriented graphs, and in a particular case, related to Caccetta Häggkvist conjecture, we improve a result of Broersma and Li obtained in 2002 (see [H.J. Broersma, X. Li, Some approaches to a conjecture on short cycles in digraphs, Discrete Appl. Math. 120 (2002) 45–53]).     

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.     

A constructive solution to a problem of ranking tournaments

A tournament is an oriented complete graph. The problem of ranking tournaments was firstly investigated by P. Erd?s and J. W. Moon. By probabilistic methods, the existence of ?? ?? unrankable” tournaments was proved. On the other hand, they also mentioned the problem of explicit constructions. However, there seems to be only a few of explicit constructions of such tournaments. In this note, we give a construction of many such tournaments by using skew Hadamard difference sets which have been investigated in combinatorial design theory.     

A dynamic distributed approach to representing proper interval graphs

First studied by Brodal and Fagerberg [G.S. Brodal, R. Fagerberg, Dynamic representation of sparse graphs, in: Algorithms and Data Structures, Proceedings of the 6th International Workshop, Vancouver, Canada, in: Lecture Notes in Computer Science, vol. 1663, Springer-Verlag, 1999], a dynamic adjacency labelling scheme labels the vertices of a graph so that the adjacency of two vertices can be deduced from their labels. The scheme is dynamic in the sense that only a small adjustment must be made to the vertex labels when a small change is made to the graph.Using a centralized dynamic representation of Hell, Shamir and Sharan [P. Hell, R. Shamir, R. Sharan, A fully dynamic algorithm for recognizing and representing proper interval graphs, SIAM Journal on Computing 31 (1) (2001) 289-305], we develop a bit/label dynamic adjacency labelling scheme for proper interval graphs. Our fully dynamic scheme handles vertex deletion/addition and edge deletion/addition in time. Furthermore, our dynamic scheme is error-detecting, as it recognizes when the new graph is not a proper interval graph.     

Tournois sans intervalle acyclique

An interval X of a tournament T is a vertex subset of T such that any vertex not in X either dominates or is dominated by all of the vertices in X. We caracterize the tournaments such that the only non empty acyclic intervals are the singletons and which are critical for that property, that is whenever a vertex is removed at least one acyclic interval with more than 2 vertices is created. These tournaments are exactly those which are the composition of any tournament with circulant tournaments. That work on acyclic intervals was motivated by the study of tournaments for which no median order forced itself naturally. To cite this article: J.-F. Culus, B. Jouve, C. R. Acad. Sci. Paris, Ser. I 341 (2005).     

Set graphs. I. Hereditarily finite sets and extensional acyclic orientations

A graph $G$ is said to be a set graph if it admits an acyclic orientation which is also extensional, in the sense that the out-neighborhoods of its vertices are pairwise distinct. Equivalently, a set graph is the underlying graph of the digraph representation of a hereditarily finite set.In this paper, we initiate the study of set graphs. On the one hand, we identify several necessary conditions that every set graph must satisfy. On the other hand, we show that set graphs form a rich class of graphs containing all connected claw-free graphs and all graphs with a Hamiltonian path. In the case of claw-free graphs, we provide a polynomial-time algorithm for finding an extensional acyclic orientation. Inspired by manipulations of hereditarily finite sets, we give simple proofs of two well-known results about claw-free graphs. We give a complete characterization of unicyclic set graphs, and point out two NP-complete problems closely related to the problem of recognizing set graphs. Finally, we argue that these three problems are solvable in linear time on graphs of bounded treewidth.     

Planar acyclic oriented graphs

A plane Hasse representation of an acyclic oriented graph is a drawing of the graph in the Euclidean plane such that all arcs are straight-line segments directed upwards and such that no two arcs cross. We characterize completely those oriented graphs which have a plane Hasse representation such that all faces are bounded by convex polygons. From this we derive the Hasse representation analogue, due to Kelly and Rival of Fary's theorem on straight-line representations of planar graphs and the Kuratowski type theorem of Platt for acyclic oriented graphs with only one source and one sink. Finally, we describe completely those acyclic oriented graphs which have a vertex dominating all other vertices and which have no plane Hasse representation, a problem posed by Trotter.