| Naslov: | The toll walk transit function of a graph: axiomatic characterizations and first-order non-definability |
|---|
| Avtorji: | ID Changat, Manoj (Avtor)
ID Jacob, Jeny (Avtor)
ID Sheela, Lekshmi Kamal K. (Avtor)
ID Peterin, Iztok (Avtor) |
|---|
| Datoteke: |  PDF - Predstavitvena datoteka, prenos (1,26 MB)
MD5: C850B80BDF02DCD542CA1AC9B73946C7
 URL - Izvorni URL, za dostop obiščite https://www.sciencedirect.com/science/article/pii/S0166218X25005347
|
|---|
| Jezik: | Angleški jezik |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: |  IMFM - Inštitut za matematiko, fiziko in mehaniko
|
|---|
| Povzetek: | 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. |
|---|
| Ključne besede: | toll walk, transit function, axioms, chordal graphs, AT-free graphs, Ptolemaic graphs, distance-hereditary graphs |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 01.02.2026 |
|---|
| Leto izida: | 2026 |
|---|
| Št. strani: | str. 128-145 |
|---|
| Številčenje: | Vol. 380 |
|---|
| PID: | 20.500.12556/DiRROS-23680  |
|---|
| UDK: | 519.17 |
|---|
| ISSN pri članku: | 0166-218X |
|---|
| DOI: | 10.1016/j.dam.2025.09.006 |
|---|
| COBISS.SI-ID: | 250159875 |
|---|
| Opomba: |
|
|---|
| Datum objave v DiRROS: | 24.09.2025 |
|---|
| Število ogledov: | 213 |
|---|
| Število prenosov: | 110 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
