Czechoslovak Mathematical Journal, Vol. 69, No. 2, pp. 295-315, 2019
Transitive closure and transitive reduction in bidirected graphs
Ouahiba Bessouf, Abdelkader Khelladi, Thomas Zaslavsky
Received December 22, 2016. Published online April 25, 2019.
Abstract: In a bidirected graph, an edge has a direction at each end, so bidirected graphs generalize directed graphs. We generalize the definitions of transitive closure and transitive reduction from directed graphs to bidirected graphs by introducing new notions of bipath and bicircuit that generalize directed paths and cycles. We show how transitive reduction is related to transitive closure and to the matroids of the signed graph corresponding to the bidirected graph.
Keywords: bidirected graph; signed graph; matroid; transitive closure; transitive reduction
References: [1] A. V. Aho, M. R. Garey, J. D. Ullman: The transitive reduction of a directed graph. SIAM J. Comput. 1 (1972), 131-137. DOI 10.1137/0201008 | MR 0306032 | Zbl 0247.05128
[2] C. Berge: Théorie des graphes et ses applications. Collection Universitaire de Mathématiques, 2, Dunod, Paris (1958). (In French.) MR 0102822 | Zbl 0088.15404
[3] O. Bessouf: Menger's Theorem in the Bidirected Graphs. Master's Thesis, Faculty of Mathematics, University of Science and Technology Houari Boumediene, Algiers (1999). (In French.)
[4] F. Harary: On the notion of balance of a signed graph. Mich. Math. J. 2 (1954), 143-146. DOI 10.1307/mmj/1028989917 | MR 0067468 | Zbl 0056.42103
[5] F. Harary: Structural duality. Behavioral Sci. 2 (1957), 255-265. DOI 10.1002/bs.3830020403 | MR 0134799
[6] A. Khelladi: Algebraic Properties of Combinative Structures. Thesis of Doctorate of State, Institute of Mathematics, University of Science and Technology Houari Boumediene, Algiers (1985). (In French.)
[7] A. Khelladi: Nowhere-zero integral chains and flows in bidirected graphs. J. Comb. Theory, Ser. B 43 (1987), 95-115. DOI 10.1016/0095-8956(87)90032-3 | MR 0897242 | Zbl 0617.90026
[8] J. Oxley: Matroid Theory. Oxford Graduate Texts in Mathematics 21, Oxford University Press, Oxford (2011). DOI 10.1093/acprof:oso/9780198566946.001.0001 | MR 2849819 | Zbl 1254.05002
[9] T. Zaslavsky: Signed graphs. Discrete Appl. Math. 4 (1982), 47-74 erratum ibid. 5 (1983), 248. DOI 10.1016/0166-218X(83)90047-1 | MR 0683518 | Zbl 0503.05060
[10] T. Zaslavsky: Orientation of signed graphs. Eur. J. Comb. 12 (1991), 361-375. DOI 10.1016/S0195-6698(13)80118-7 | MR 1120422 | Zbl 0761.05095
Affiliations: Ouahiba Bessouf, (corresponding author), Abdelkader Khelladi, Faculty of Mathematics, University of Science and Technology Houari Boumediene, BP 32 El Alia, Bab-Ezzouar 16111, Algiers, Algeria, e-mail: obessouf@yahoo.fr; aekhelladi@gmail.com; Thomas Zaslavsky, Department of Mathematical Sciences, Binghamton University, Binghamton, NY 13902-6000, USA, e-mail: zaslav@math.binghamton.edu
