Jump number of dags having Dilworth number 2

The jump number, denoted by σ, of a directed acyclic graph (dag) G, is the minimum number of arcs that have to be added to G such that the resulting graph is still acyclic and has a hamiltonian path.We study here the particular class of dags having an induced partial order of width 2, and give a characterization of such graphs with σ(G)=i. This yields immediately a polynomial algorithm to compute the jump number in this particular class.     

On a relation between the domination number and a strongly connected bidirection of an undirected graph

As a generalization of directed and undirected graphs, Edmonds and Johnson [J. Edmonds, E.L. Johnson, Matching: A well-solved class of linear programs, in: R. Guy, H. Hanani, N. Sauer, J. Schönheim (Eds.), Combinatorial Structures and their Applications, Gordon and Breach, New York, 1970, pp. 88-92] introduced bidirected graphs. A bidirected graph is a graph each arc of which has either two positive end-vertices (tails), two negative end-vertices (heads), or one positive end-vertex (tail) and one negative end-vertex (head). We extend the notion of directed paths, distance, diameter and strong connectivity from directed to bidirected graphs and characterize those undirected graphs that allow a strongly connected bidirection. Considering the problem of finding the minimum diameter of all strongly connected bidirections of a given undirected graph, we generalize a result of Fomin et al. [F.V. Fomin, M. Matamala, E. Prisner, I. Rapaport, Bilateral orientations in graphs: Domination and AT-free classes, in: Proceedings of the Brazilian Symposium on Graphs, Algorithms and Combinatorics, GRACO 2001, in: Electronics Notes in Discrete Mathematics, vol. 7, Elsevier Science Publishers, 2001] about directed graphs and obtain an upper bound for the minimum diameter which depends on the minimum size of a dominating set and the number of bridges in the undirected graph.     

On some balanced, totally balanced and submodular delivery games

This paper studies a class of delivery problems associated with the Chinese postman problem and a corresponding class of delivery games. A delivery problem in this class is determined by a connected graph, a cost function defined on its edges and a special chosen vertex in that graph which will be referred to as the post office. It is assumed that the edges in the graph are owned by different individuals and the delivery game is concerned with the allocation of the traveling costs incurred by the server, who starts at the post office and is expected to traverse all edges in the graph before returning to the post office. A graph G is called Chinese postman-submodular, or, for short, CP-submodular (CP-totally balanced, CP-balanced, respectively) if for each delivery problem in which G is the underlying graph the associated delivery game is submodular (totally balanced, balanced, respectively). For undirected graphs we prove that CP-submodular graphs and CP-totally balanced graphs are weakly cyclic graphs and conversely. An undirected graph is shown to be CP-balanced if and only if it is a weakly Euler graph. For directed graphs, CP-submodular graphs can be characterized by directed weakly cyclic graphs. Further, it is proven that any strongly connected directed graph is CP-balanced. For mixed graphs it is shown that a graph is CP-submodular if and only if it is a mixed weakly cyclic graph. Finally, we note that undirected, directed and mixed weakly cyclic graphs can be recognized in linear time. Received May 20, 1997 / Revised version received August 18, 1998?Published online June 11, 1999     

Relations between the Local Chromatic Number and Its Directed Version

The local chromatic number is a coloring parameter defined as the minimum number of colors that should appear in the most colorful closed neighborhood of a vertex under any proper coloring of the graph. Its directed version is the same when we consider only outneighborhoods in a directed graph. For digraphs with all arcs being present in both directions the two values are obviously equal. Here, we consider oriented graphs. We show the existence of a graph where the directed local chromatic number of all oriented versions of the graph is strictly less than the local chromatic number of the underlying undirected graph. We show that for fractional versions the analogous problem has a different answer: there always exists an orientation for which the directed and undirected values coincide. We also determine the supremum of the possible ratios of these fractional parameters, which turns out to be e, the basis of the natural logarithm.     

Nombres de ramsey dans le cas orienté

Given two directed graphs G₁, G₂, the Ramsey number R(G₁,G₂) is the smallest integer n such that for any partition {U₁,U₂} of the arcs of the complete symmetric directed graph K¹_n, there exists an integer i such that the partial graph generated by U_i contains G_i as a subgraph. In this article, we determine R(P?_m,D?_n) and R(D?_m,D?_n) for some values of m and n, where P?_m denotes the directed path having m vertices and D?_m is obtained from P?_m by adding an arc from the initial vertex of P?_m to the terminal vertex.     

Fast parallel strong orientation of mixed graphs and related augmentation problems

The strong orientation problem is: Given an undirected graph, G, assign orientations to its edges so that the resulting directed graph is strongly connected. Robbins showed when such an orientation exists. A generalization of this problem is when the input graph is mixed (i.e., contains some directed and some undirected edges). Boesch and Tindell gave necessary and sufficient conditions for a strong orientation to exist in a mixed graph. In this paper we give an NC algorithm for constructing a strong orientation for a given mixed graph after determining if it exists. We also give an NC algorithm for adding a minimum set of arcs to a mixed graph to make it strongly orientable. We give simplified NC algorithms for the following special cases: find minimum augmentations to make a digraph strongly connected and to make an undirected graph bridge-connected. All the algorithms presented run within the time and processor bounds required for computing the transitive closure of a digraph.     

On multiplicative graphs and the product conjecture

We study the following problem: which graphsG have the property that the class of all graphs not admitting a homomorphism intoG is closed under taking the product (conjunction)? Whether all undirected complete graphs have the property is a longstanding open problem due to S. Hedetniemi. We prove that all odd undirected cycles and all prime-power directed cycles have the property. The former result provides the first non-trivial infinite family of undirected graphs known to have the property, and the latter result verifies a conjecture of Ne?et?il and Pultr These results allow us (in conjunction with earlier results of Ne?et?il and Pultr [17], cf also [7]) to completely characterize all (finite and infinite, directed and undirected) paths and cycles having the property. We also derive the property for a wide class of 3-chromatic graphs studied by Gerards, [5].     

On short cycles in triangle-free oriented graphs

An orientation of a simple graph is referred to as an oriented graph. Caccetta and Häggkvist conjectured that any digraph on n vertices with minimum outdegree d contains a directed cycle of length at most ?n/d?. In this paper, we consider short cycles in oriented graphs without directed triangles. Suppose that α0 is the smallest real such that every n-vertex digraph with minimum outdegree at least α₀n contains a directed triangle. Let ε < (3 ? 2α₀)/(4 ? 2α₀) be a positive real. We show that if D is an oriented graph without directed triangles and has minimum outdegree and minimum indegree at least (1/(4 ? 2α₀)+ε)|D|, then each vertex of D is contained in a directed cycle of length l for each 4 ≤ l < (4 ? 2α₀)ε|D|/(3 ? 2α₀) + 2.     

Queue layouts of iterated line directed graphs

In this paper, we study queue layouts of iterated line directed graphs. A k-queue layout of a directed graph consists of a linear ordering of the vertices and an assignment of each arc to exactly one of the k queues so that any two arcs assigned to the same queue do not nest. The queuenumber of a directed graph is the minimum number of queues required for a queue layout of the directed graph.We present upper and lower bounds on the queuenumber of an iterated line directed graph L^k(G) of a directed graph G. Our upper bound depends only on G and is independent of the number of iterations k. Queue layouts can be applied to three-dimensional drawings. From the results on the queuenumber of L^k(G), it is shown that for any fixed directed graph G, L^k(G) has a three-dimensional drawing with O(n) volume, where n is the number of vertices in L^k(G). These results are also applied to specific families of iterated line directed graphs such as de Bruijn, Kautz, butterfly, and wrapped butterfly directed graphs. In particular, the queuenumber of k-ary butterfly directed graphs is determined if k is odd.     

Branch-and-cut algorithms for the undirected m-Peripatetic Salesman Problem

In the m-Peripatetic Salesman Problem (m-PSP) the aim is to determine m edge disjoint Hamiltonian cycles of minimum total cost on a graph. This article describes exact branch-and-cut solution procedures for the undirected m-PSP. Computational results are reported on random and Euclidean graphs.     

Minimum sum set coloring of trees and line graphs of trees

In this paper, we study the minimum sum set coloring (MSSC) problem which consists in assigning a set of x(v) positive integers to each vertex v of a graph so that the intersection of sets assigned to adjacent vertices is empty and the sum of the assigned set of numbers to each vertex of the graph is minimum. The MSSC problem occurs in two versions: non-preemptive and preemptive. We show that the MSSC problem is strongly NP-hard both in the preemptive case on trees and in the non-preemptive case in line graphs of trees. Finally, we give exact parameterized algorithms for these two versions on trees and line graphs of trees.     

Counting strongly‐connected,moderately sparse directed graphs

A sharp asymptotic formula for the number of strongly connected digraphs on n labelled vertices with m arcs, under the condition m ‐ n ? n^2/3, m = O(n), is obtained; this provides a partial solution of a problem posed by Wright back in 1977. This formula is a counterpart of a classic asymptotic formula, due to Bender, Canfield and McKay, for the total number of connected undirected graphs on n vertices with m edges. A key ingredient of their proof was a recurrence equation for the connected graphs count due to Wright. No analogue of Wright's recurrence seems to exist for digraphs. In a previous paper with Nick Wormald we rederived the BCM formula by counting first connected graphs among the graphs of minimum degree 2, at least. In this paper, using a similar embedding for directed graphs, we find an asymptotic formula, which includes an explicit error term, for the fraction of strongly‐connected digraphs with parameters m and n among all such digraphs with positive in/out‐degrees. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Some remarks on Arc-connectivity,vertex splitting,and orientation in graphs and digraphs

We apply proof techniques developed by L. Lovász and A. Frank to obtain several results on the arc-connectivity of graphs and digraphs. The first results concern the operation of splitting two arcs from a vertex of an Eulerian graph or digraph in such a way as to preserve local connectivity conditions. The final result is concerned with orienting the edges of a mixed graph (consisting of vertices, undirected edges, and directed arcs) in such a way that the resulting digraph is as arc-connected as possible.     

Influence Digraphs Induced by Time-Stamped Graphs (Extended Abstract)

A time-stamped graph is an undirected graph with a real number on each edge. Vertex u influences vertex v if there is an increasing path from u to v. The induced influence digraph of a time-stamped graph is the directed graph that records the influences. In this paper we study the realizability problem: Given a parameter value, does there exist a time-stamped graph whose induced influence digraph has the given parameter value? In particular, we solve this problem when the parameter is the number of arcs. Moreover, if the candidates for the time-stamped graphs are restricted to trees, then every realizable value can be achieved by a tree homeomorphic to K₂ or K_1,3. A number of other questions are also explored. The full version of this paper is submitted to a referreed journal.     

On directed local chromatic number,shift graphs,and Borsuk‐like graphs

We investigate the local chromatic number of shift graphs and prove that it is close to their chromatic number. This implies that the gap between the directed local chromatic number of an oriented graph and the local chromatic number of the underlying undirected graph can be arbitrarily large. We also investigate the minimum possible directed local chromatic number of oriented versions of “topologically t‐chromatic” graphs. We show that this minimum for large enough t‐chromatic Schrijver graphs and t‐chromatic generalized Mycielski graphs of appropriate parameters is ?t/4?+1. © 2010 Wiley Periodicals, Inc. J Graph Theory 66: 65‐82, 2010     

A Vizing-type theorem for matching forests

A well-known Theorem of Vizing states that one can colour the edges of a graph by Δ+ colours, such that edges of the same colour form a matching. Here, Δ denotes the maximum degree of a vertex, and the maximum multiplicity of an edge in the graph. An analogue of this Theorem for directed graphs was proved by Frank. It states that one can colour the arcs of a digraph by Δ+ colours, such that arcs of the same colour form a branching. For a digraph, Δ denotes the maximum indegree of a vertex, and the maximum multiplicity of an arc. We prove a common generalization of the above two theorems concerning the colouring of mixed graphs (these are graphs having both directed and undirected edges) in such a way that edges of the same colour form a matching forest.     

The Steiner connectivity problem

The Steiner connectivity problem has the same significance for line planning in public transport as the Steiner tree problem for telecommunication network design. It consists in finding a minimum cost set of elementary paths to connect a subset of nodes in an undirected graph and is, therefore, a generalization of the Steiner tree problem. We propose an extended directed cut formulation for the problem which is, in comparison to the canonical undirected cut formulation, provably strong, implying, e.g., a class of facet defining Steiner partition inequalities. Since a direct application of this formulation is computationally intractable for large instances, we develop a partial projection method to produce a strong relaxation in the space of canonical variables that approximates the extended formulation. We also investigate the separation of Steiner partition inequalities and give computational evidence that these inequalities essentially close the gap between undirected and extended directed cut formulation. Using these techniques, large Steiner connectivity problems with up to 900 nodes can be solved within reasonable optimality gaps of typically less than five percent.     

Decomposing Oriented Graphs into Six Locally Irregular Oriented Graphs

An undirected graph G is locally irregular if every two of its adjacent vertices have distinct degrees. We say that G is decomposable into k locally irregular graphs if there exists a partition \(E_1 \cup E_2 \cup \cdots \cup E_k\) of the edge set E(G) such that each \(E_i\) induces a locally irregular graph. It was recently conjectured by Baudon et al. that every undirected graph admits a decomposition into at most three locally irregular graphs, except for a well-characterized set of indecomposable graphs. We herein consider an oriented version of this conjecture. Namely, can every oriented graph be decomposed into at most three locally irregular oriented graphs, i.e. whose adjacent vertices have distinct outdegrees? We start by supporting this conjecture by verifying it for several classes of oriented graphs. We then prove a weaker version of this conjecture. Namely, we prove that every oriented graph can be decomposed into at most six locally irregular oriented graphs. We finally prove that even if our conjecture were true, it would remain NP-complete to decide whether an oriented graph is decomposable into at most two locally irregular oriented graphs.     

Partial Characterizations of Circular-Arc Graphs

A circular-arc graph is the intersection graph of a family of arcs on a circle. A characterization by forbidden induced subgraphs for this class of graphs is not known, and in this work we present a partial result in this direction. We characterize circular-arc graphs by a list of minimal forbidden induced subgraphs when the graph belongs to the following classes: diamond-free graphs, P₄-free graphs, paw-free graphs, and claw-free chordal graphs.     

Branch-and-cut approaches for chance-constrained formulations of reliable network design problems

We study solution approaches for the design of reliably connected networks. Specifically, given a network with arcs that may fail at random, the goal is to select a minimum cost subset of arcs such the probability that a connectivity requirement is satisfied is at least $1 - \epsilon $ , where $\epsilon $ is a risk tolerance. We consider two types of connectivity requirements. We first study the problem of requiring an $s$ - $t$ path to exist with high probability in a directed graph. Then we consider undirected graphs, where we require the graph to be fully connected with high probability. We model each problem as a stochastic integer program with a joint chance constraint, and present two formulations that can be solved by a branch-and-cut algorithm. The first formulation uses binary variables to represent whether or not the connectivity requirement is satisfied in each scenario of arc failures and is based on inequalities derived from graph cuts in individual scenarios. We derive additional valid inequalities for this formulation and study their facet-inducing properties. The second formulation is based on probabilistic graph cuts, an extension of graph cuts to graphs with random arc failures. Inequalities corresponding to probabilistic graph cuts are sufficient to define the set of feasible solutions and violated inequalities in this class can be found efficiently at integer solutions, allowing this formulation to be solved by a branch-and-cut algorithm. Computational results demonstrate that the approaches can effectively solve instances on large graphs with many failure scenarios. In addition, we demonstrate that, by varying the risk tolerance, our model yields a rich set of solutions on the efficient frontier of cost and reliability.