An approach for the Steiner problem in directed graphs

We present a scheme to solve the Steiner problem in directed graphs using a heuristic method to obtain upper bounds and thek shortest arborescences algorithm to compute lower bounds. We propose to combine these ideas in an enumerative algorithm. Computational results are presented for both thek shortest arborescences algorithm and the heuristic method, including reduction tests for the problem.This work was partially supported by CNP_q, FINEP, CAPES and IBM do Brasil.     

On weighted directed graphs

The study of a mixed graph and its Laplacian matrix have gained quite a bit of interest among the researchers. Mixed graphs are very important for the study of graph theory as they provide a setup where one can have directed and undirected edges in the graph. In this article we present a more general structure, namely the weighted directed graphs and supply appropriate generalizations of several existing results for mixed graphs related to singularity of the corresponding Laplacian matrix. We also prove many new combinatorial results relating the Laplacian matrix and the graph structure.     

On antimagic directed graphs

An antimagic labeling of an undirected graph G with n vertices and m edges is a bijection from the set of edges of G to the integers {1, …, m} such that all n vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with that vertex. A graph is called antimagic if it admits an antimagic labeling. In (N. Hartsfield and G. Ringel, Pearls in Graph Theory, Academic Press, Boston, 1990, pp. 108–109), Hartsfield and Ringel conjectured that every simple connected graph, other than K₂, is antimagic. Despite considerable effort in recent years, this conjecture is still open. In this article we study a natural variation; namely, we consider antimagic labelings of directed graphs. In particular, we prove that every directed graph whose underlying undirected graph is “dense” is antimagic, and that almost every undirected d‐regular graph admits an orientation which is antimagic. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 219–232, 2010     

A model of the coNP-complete non-Hamilton tour decision problem for directed graphs

A truncated permutation matrix polytope is defined as the convex hull of a proper subset of n-permutations represented as 0/1 matrices. We present a linear system that models the coNP-complete non-Hamilton tour decision problem based upon constructing the convex hull of a set of truncated permutation matrix polytopes. Define polytope P^n–1 as the convex hull of all n-1 by n-1 permutation matrices. Each extreme point of P^n–1 is placed in correspondence (a bijection) with each Hamilton tour of a complete directed graph on n vertices. Given any n vertex graph G_n, a polynomial sized linear system F⁽ⁿ⁾ is constructed for which the image of its solution set, under an orthogonal projection, is the convex hull of the complete set of extrema of a subset of truncated permutation matrix polytopes, where each extreme point is in correspondence with each Hamilton tour not in G_n. The non-Hamilton tour decision problem is modeled by F⁽ⁿ⁾ such that G_n is non-Hamiltonian if and only if, under an orthogonal projection, the image of the solution set of F⁽ⁿ⁾ is P^n–1. The decision problem Is the projection of the solution set of F⁽ⁿ⁾=P^n–1? is therefore coNP-complete, and this particular model of the non-Hamilton tour problem appears to be new.Dedicated to the 250+ families in Kelowna BC, who lost their homes due to forest fires in 2003.I visited Ted at his home in Kelowna during this time - his family opened their home to evacuees and we shared happy and sad times with many wonderful people.     

On maximal circuits in directed graphs

An exact bound is obtained for the number of edges in a directed graph which ensures the existence of a circuit exceeding a prescribed length.Another proof of an analogous result of Erdös and Gallai for undirected graphs is supplied in the Appendix.     

The maximum integer multiterminal flow problem in directed graphs

Given an arc-capacitated digraph and k terminal vertices, the directed maximum integer multiterminal flow problem is to route the maximum number of flow units between the terminals. We introduce a new parameter k_L?k for this problem and study its complexity with respect to k_L.     

On directed zero-divisor graphs of finite rings

For an artinian ring R, the directed zero-divisor graph Γ(R) is connected if and only if there is no proper one-sided identity element in R. Sinks and sources are characterized and clarified for a finite ring R. Especially, it is proved that for any ring R, if there exists a source y in Γ(R) with y²=0, then |R|=4 and R={0,x,y,z}, where x and z are left identity elements and yx=0=yz. Such a ring R is also the only ring such that Γ(R) has exactly one source. This shows that Γ(R) cannot be a network for any finite or infinite ring R.     

On the generalized directed rural postman problem

The generalized directed rural postman problem (GDRPP) is a generic type of arc routing problem. In the present paper, it is described how many types of practically relevant single-vehicle routing problems can be modelled as GDRPPs. This demonstrates the versatility of the GDRPP and its importance as a unified model for postman problems. In addition, an exact and a heuristic solution method are presented. Computational experiments using two large sets of benchmark instances are performed. The results show high solution quality and thus demonstrate the practical usefulness of the approach.     

On semiprojectivity of -algebras of directed graphs

It is shown that if is a countable, transitive directed graph with finitely many vertices, then is semiprojective.

     

On directed graphs with an independent covering set

We prove that if a directed graph,D, contains no odd directed cycle and, for all but finitely many vertices, EITHER the in-degrees are finite OR the out-degrees are at most one, thenD contains an independent covering set (i.e. there is a kernel). We also give an example of a countable directed graph which has no directed cycle, each vertex has out-degree at most two, and which has no independent covering set.Research supported by N.S.E.R.C. grants #69-0982 and #69-0259.     

On a cyclic connectivity property of directed graphs

Let us call a digraph D cycle-connected if for every pair of vertices u,v∈V(D) there exists a cycle containing both u and v. In this paper we study the following open problem introduced by Ádám. Let D be a cycle-connected digraph. Does there exist a universal edge in D, i.e., an edge e∈E(D) such that for every w∈V(D) there exists a cycle C such that w∈V(C) and e∈E(C)?In his 2001 paper Hetyei conjectured that cycle-connectivity always implies the existence of a universal edge. In the present paper we prove the conjecture of Hetyei for bitournaments.