Thomas Zaslavsky (Binghamton)

Transitive Closure in Digraphs and Bidigraphs

Abstract for the Combinatorics Seminar
2019 February 5

In a directed graph transitive closure means that directed edges (u,v) and (v,w) imply directed edge (u,w). Ouihaba Bessouf and Abdelkader Khelladi, with some help from me, have generalized this concept to bidirected graphs, where each edge has a separate arrow at each end. Since bidirected graphs are oriented signed graphs and directed graphs are oriented all-positive signed graphs, the generalization should, and does, include the theory of transitive closure in directed graphs.

We studied three aspects of transitive closure in bidirected graphs. First is transitive closure itself: how to compute it and to find the structure of bidirected graphs that are transitively closed. Second is transitive reduction: finding subgraphs whose transitive closure equals that of the original bidirected graph. Third is the connection between transitive closure and quasibalance of the signed graph, an idea of Khelladi's inspired by the matroid of the signed graph.

I will attempt to flesh out all these ideas in the hour seminar.


To the Combinatorics Seminar Web page.