| Title:
|
Transitive closure and transitive reduction in bidirected graphs (English) |
| Author:
|
Bessouf, Ouahiba |
| Author:
|
Khelladi, Abdelkader |
| Author:
|
Zaslavsky, Thomas |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
69 |
| Issue:
|
2 |
| Year:
|
2019 |
| Pages:
|
295-315 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
bidirected graph |
| Keyword:
|
signed graph |
| Keyword:
|
matroid |
| Keyword:
|
transitive closure |
| Keyword:
|
transitive reduction |
| MSC:
|
05C20 |
| MSC:
|
05C22 |
| MSC:
|
05C38 |
| idZBL:
|
Zbl 07088785 |
| idMR:
|
MR3959945 |
| DOI:
|
10.21136/CMJ.2019.0644-16 |
| . |
| Date available:
|
2019-05-24T08:54:14Z |
| Last updated:
|
2021-07-05 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/147724 |
| . |
| Reference:
|
[1] Aho, A. V., Garey, M. R., Ullman, J. D.: The transitive reduction of a directed graph.SIAM J. Comput. 1 (1972), 131-137. Zbl 0247.05128, MR 0306032, 10.1137/0201008 |
| Reference:
|
[2] Berge, C.: Théorie des graphes et ses applications.Collection Universitaire de Mathématiques, 2, Dunod, Paris French (1958). Zbl 0088.15404, MR 0102822 |
| Reference:
|
[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). |
| Reference:
|
[4] Harary, F.: On the notion of balance of a signed graph.Mich. Math. J. 2 (1954), 143-146. Zbl 0056.42103, MR 0067468, 10.1307/mmj/1028989917 |
| Reference:
|
[5] Harary, F.: Structural duality.Behavioral Sci. 2 (1957), 255-265. MR 0134799, 10.1002/bs.3830020403 |
| Reference:
|
[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). |
| Reference:
|
[7] Khelladi, A.: Nowhere-zero integral chains and flows in bidirected graphs.J. Comb. Theory, Ser. B 43 (1987), 95-115. Zbl 0617.90026, MR 0897242, 10.1016/0095-8956(87)90032-3 |
| Reference:
|
[8] Oxley, J.: Matroid Theory.Oxford Graduate Texts in Mathematics 21, Oxford University Press, Oxford (2011). Zbl 1254.05002, MR 2849819, 10.1093/acprof:oso/9780198566946.001.0001 |
| Reference:
|
[9] Zaslavsky, T.: Signed graphs.Discrete Appl. Math. 4 (1982), 47-74 erratum ibid. 5 1983 248. Zbl 0503.05060, MR 0683518, 10.1016/0166-218X(83)90047-1 |
| Reference:
|
[10] Zaslavsky, T.: Orientation of signed graphs.Eur. J. Comb. 12 (1991), 361-375. Zbl 0761.05095, MR 1120422, 10.1016/S0195-6698(13)80118-7 |
| . |
