| Title: | The toll walk transit function of a graph: axiomatic characterizations and first-order non-definability |
|---|
| Authors: | ID Changat, Manoj (Author)
ID Jacob, Jeny (Author)
ID Sheela, Lekshmi Kamal K. (Author)
ID Peterin, Iztok (Author) |
|---|
| Files: |  PDF - Presentation file, download (1,26 MB)
MD5: C850B80BDF02DCD542CA1AC9B73946C7
 URL - Source URL, visit https://www.sciencedirect.com/science/article/pii/S0166218X25005347
|
|---|
| Language: | English |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: |  IMFM - Institute of Mathematics, Physics, and Mechanics
|
|---|
| Abstract: | A walk $W=w_1w_2\dots w_k$, $k\geq 2$, is called a toll walk if $w_1\neq w_k$ and $w_2(w_{k-1})$ are the only neighbors of $w_1(w_k)$ on $W$ in a graph $G$. A toll walk interval $T(u,v)$, $u,v\in V(G)$, contains all the vertices that belong to a toll walk between $u$ and $v$. The toll walk intervals yield a toll walk transit function $T:V(G)\times V(G)\rightarrow 2^{V(G)}$. We represent several axioms that characterize the toll walk transit function among chordal graphs, trees, asteroidal triple-free graphs, Ptolemaic graphs, and distance hereditary graphs. We also show that the toll walk transit function can not be described in the language of first-order logic for an arbitrary graph. |
|---|
| Keywords: | toll walk, transit function, axioms, chordal graphs, AT-free graphs, Ptolemaic graphs, distance-hereditary graphs |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Publication date: | 01.02.2026 |
|---|
| Year of publishing: | 2026 |
|---|
| Number of pages: | str. 128-145 |
|---|
| Numbering: | Vol. 380 |
|---|
| PID: | 20.500.12556/DiRROS-23680  |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 0166-218X |
|---|
| DOI: | 10.1016/j.dam.2025.09.006 |
|---|
| COBISS.SI-ID: | 250159875 |
|---|
| Note: |
|
|---|
| Publication date in DiRROS: | 24.09.2025 |
|---|
| Views: | 224 |
|---|
| Downloads: | 116 |
|---|
| Metadata: |    |
|---|
|
:
|
Copy citation |
|---|
| | | | Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
