| Title:
|
The directed geodetic structure of a strong digraph (English) |
| Author:
|
Nebeský, Ladislav |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
54 |
| Issue:
|
1 |
| Year:
|
2004 |
| Pages:
|
1-8 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
By a ternary structure we mean an ordered pair $(U_0, T_0)$, where $U_0$ is a finite nonempty set and $T_0$ is a ternary relation on $U_0$. A ternary structure $(U_0, T_0)$ is called here a directed geodetic structure if there exists a strong digraph $D$ with the properties that $V(D) = U_0$ and \[ T_0(u, v, w)\quad \text{if} \text{and} \text{only} \text{if}\quad d_D(u, v) + d_D(v, w) = d_D(u, w) \] for all $u, v, w \in U_0$, where $d_D$ denotes the (directed) distance function in $D$. It is proved in this paper that there exists no sentence ${\mathbf s}$ of the language of the first-order logic such that a ternary structure is a directed geodetic structure if and only if it satisfies ${\mathbf s}$. (English) |
| Keyword:
|
strong digraph |
| Keyword:
|
directed distance |
| Keyword:
|
ternary relation |
| Keyword:
|
finite structure |
| MSC:
|
03C13 |
| MSC:
|
05C12 |
| MSC:
|
05C20 |
| idZBL:
|
Zbl 1045.05039 |
| idMR:
|
MR2040215 |
| . |
| Date available:
|
2009-09-24T11:09:07Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/127861 |
| . |
| Reference:
|
[1] G. Chartrand and L. Lesniak: Graphs & Digraphs.Chapman & Hall, London, 1996. MR 1408678 |
| Reference:
|
[2] H-D. Ebbinghaus and J. Flum: Finite Model Theory.Springer-Verlag, Berlin, 1995. MR 1409813 |
| Reference:
|
[3] H. M. Mulder: The interval function of a graph.Math. Centre Tracts 132, Math Centre, Amsterdam, 1980. Zbl 0446.05039, MR 0605838 |
| Reference:
|
[4] L. Nebeský: A characterization of the interval function of a connected graph.Czechoslovak Math. J. 44(119) (1994), 173–178. MR 1257943 |
| Reference:
|
[5] L. Nebeský: Characterizing the interval function of a connected graph.Math. Bohem. 123 (1998), 137–144. MR 1673965 |
| Reference:
|
[6] L. Nebeský: The interval function of a connected graph and a characterization of geodetic graphs.Math. Bohem. 126 (2001), 247–254. MR 1826487 |
| Reference:
|
[7] L. Nebeský: The induced paths in a connected graph and a ternary relation determined by them.Math. Bohem. 127 (2002), 397–408. MR 1931324 |
| . |
