Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
strong digraph; directed distance; ternary relation; finite structure
strong digraph; directed distance; ternary relation; finite structure
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}$.
References:
[1] G. Chartrand and L. Lesniak: Graphs & Digraphs. Chapman & Hall, London, 1996. MR 1408678
[2] H-D. Ebbinghaus and J. Flum: Finite Model Theory. Springer-Verlag, Berlin, 1995. MR 1409813
[3] H. M. Mulder: The interval function of a graph. Math. Centre Tracts 132, Math Centre, Amsterdam, 1980. MR 0605838 | Zbl 0446.05039
[4] L. Nebeský: A characterization of the interval function of a connected graph. Czechoslovak Math. J. 44(119) (1994), 173–178. MR 1257943
[5] L. Nebeský: Characterizing the interval function of a connected graph. Math. Bohem. 123 (1998), 137–144. MR 1673965
[6] L. Nebeský: The interval function of a connected graph and a characterization of geodetic graphs. Math. Bohem. 126 (2001), 247–254. MR 1826487
[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
Search
Partner of
