Directed Transit Functions
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910521521864704 |
|---|---|
| author | Anil, Arun Changat, Manoj K-Sheela, Lekshmi Kamal Shanavas, Ameera Vaheeda Chavara, John J. Narasimha-Shenoi, Prasanth G. Schmidt, Bruno J. Stadler, Peter F. |
| author_facet | Anil, Arun Changat, Manoj K-Sheela, Lekshmi Kamal Shanavas, Ameera Vaheeda Chavara, John J. Narasimha-Shenoi, Prasanth G. Schmidt, Bruno J. Stadler, Peter F. |
| contents | Transit functions were introduced as models of betweenness on undirected structures. Here we introduce directed transit function as the directed analogue on directed structures such as posets and directed graphs. We first show that betweenness in posets can be expressed by means of a simple set of first order axioms. Similar characterizations can be obtained for graphs with natural partial orders, in particular, forests, trees, and mangroves. Relaxing the acyclicity conditions leads to a generalization of the well-known geometric transit function to the directed structures. Moreover, we discuss some properties of the directed analogues of prominent transit functions, including the all-paths, induced paths, and shortest paths (or interval) transit functions. Finally we point out some open questions and directions for future work. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_07741 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Directed Transit Functions Anil, Arun Changat, Manoj K-Sheela, Lekshmi Kamal Shanavas, Ameera Vaheeda Chavara, John J. Narasimha-Shenoi, Prasanth G. Schmidt, Bruno J. Stadler, Peter F. Combinatorics Discrete Mathematics 05C38, 05C69, 05C99 Transit functions were introduced as models of betweenness on undirected structures. Here we introduce directed transit function as the directed analogue on directed structures such as posets and directed graphs. We first show that betweenness in posets can be expressed by means of a simple set of first order axioms. Similar characterizations can be obtained for graphs with natural partial orders, in particular, forests, trees, and mangroves. Relaxing the acyclicity conditions leads to a generalization of the well-known geometric transit function to the directed structures. Moreover, we discuss some properties of the directed analogues of prominent transit functions, including the all-paths, induced paths, and shortest paths (or interval) transit functions. Finally we point out some open questions and directions for future work. |
| title | Directed Transit Functions |
| topic | Combinatorics Discrete Mathematics 05C38, 05C69, 05C99 |
| url | https://arxiv.org/abs/2407.07741 |