Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
bidirected graph; signed graph; matroid; transitive closure; transitive reduction
bidirected graph; signed graph; matroid; transitive closure; transitive reduction
Summary:
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.
References:
[1] Aho, A. V., Garey, M. R., Ullman, J. D.: The transitive reduction of a directed graph. SIAM J. Comput. 1 (1972), 131-137. DOI 10.1137/0201008 | MR 0306032 | Zbl 0247.05128
[2] Berge, C.: Théorie des graphes et ses applications. Collection Universitaire de Mathématiques, 2, Dunod, Paris French (1958). MR 0102822 | Zbl 0088.15404
[3] Bessouf, O.: Menger's Theorem in the Bidirected Graphs. Master's Thesis, Faculty of Mathematics, University of Science and Technology Houari Boumediene, Algiers French (1999).
[4] Harary, F.: 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] Harary, F.: Structural duality. Behavioral Sci. 2 (1957), 255-265. DOI 10.1002/bs.3830020403 | MR 0134799
[6] Khelladi, A.: Algebraic Properties of Combinative Structures. Thesis of Doctorate of State, Institute of Mathematics, University of Science and Technology Houari Boumediene, Algiers French (1985).
[7] Khelladi, A.: 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] Oxley, J.: 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] Zaslavsky, T.: 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] Zaslavsky, T.: Orientation of signed graphs. Eur. J. Comb. 12 (1991), 361-375. DOI 10.1016/S0195-6698(13)80118-7 | MR 1120422 | Zbl 0761.05095
Search
Partner of
