Geodesic
The induced paths in a connected graph and a ternary relation determined by them
Mathematica Bohemica, Tome 127 (2002) no. 3, pp. 397-408
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

By a ternary structure we mean an ordered pair $(X_0, T_0)$, where $X_0$ is a finite nonempty set and $T_0$ is a ternary relation on $X_0$. By the underlying graph of a ternary structure $(X_0, T_0)$ we mean the (undirected) graph $G$ with the properties that $X_0$ is its vertex set and distinct vertices $u$ and $v$ of $G$ are adjacent if and only if \[\lbrace x \in X_0\; T_0(u, x, v)\rbrace \cup \lbrace x \in X_0\; T_0(v, x, u)\rbrace = \lbrace u, v\rbrace .\] A ternary structure $(X_0, T_0)$ is said to be the B-structure of a connected graph $G$ if $X_0$ is the vertex set of $G$ and the following statement holds for all $u, x, y \in X_0$: $T_0(x, u, y)$ if and only if $u$ belongs to an induced $x-y$ path in $G$. It is clear that if a ternary structure $(X_0, T_0)$ is the B-structure of a connected graph $G$, then $G$ is the underlying graph of $(X_0, T_0)$. We will prove that there exists no sentence $\sigma $ of the first-order logic such that a ternary structure $(X_0, T_0)$ with a connected underlying graph $G$ is the B-structure of $G$ if and only if $(X_0, T_0)$ satisfies $\sigma $.
By a ternary structure we mean an ordered pair $(X_0, T_0)$, where $X_0$ is a finite nonempty set and $T_0$ is a ternary relation on $X_0$. By the underlying graph of a ternary structure $(X_0, T_0)$ we mean the (undirected) graph $G$ with the properties that $X_0$ is its vertex set and distinct vertices $u$ and $v$ of $G$ are adjacent if and only if \[\lbrace x \in X_0\; T_0(u, x, v)\rbrace \cup \lbrace x \in X_0\; T_0(v, x, u)\rbrace = \lbrace u, v\rbrace .\] A ternary structure $(X_0, T_0)$ is said to be the B-structure of a connected graph $G$ if $X_0$ is the vertex set of $G$ and the following statement holds for all $u, x, y \in X_0$: $T_0(x, u, y)$ if and only if $u$ belongs to an induced $x-y$ path in $G$. It is clear that if a ternary structure $(X_0, T_0)$ is the B-structure of a connected graph $G$, then $G$ is the underlying graph of $(X_0, T_0)$. We will prove that there exists no sentence $\sigma $ of the first-order logic such that a ternary structure $(X_0, T_0)$ with a connected underlying graph $G$ is the B-structure of $G$ if and only if $(X_0, T_0)$ satisfies $\sigma $.
DOI : 10.21136/MB.2002.134072
Classification : 03C13, 05C38
Keywords: connected graph; induced path; ternary relation; finite structure 
@article{10_21136_MB_2002_134072,
     author = {Nebesk\'y, Ladislav},
     title = {The induced paths in a connected graph and a ternary relation determined by them},
     journal = {Mathematica Bohemica},
     pages = {397--408},
     year = {2002},
     volume = {127},
     number = {3},
     doi = {10.21136/MB.2002.134072},
     mrnumber = {1931324},
     zbl = {1003.05063},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2002.134072/}
}
TY  - JOUR
AU  - Nebeský, Ladislav
TI  - The induced paths in a connected graph and a ternary relation determined by them
JO  - Mathematica Bohemica
PY  - 2002
SP  - 397
EP  - 408
VL  - 127
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2002.134072/
DO  - 10.21136/MB.2002.134072
LA  - en
ID  - 10_21136_MB_2002_134072
ER  - 
%0 Journal Article
%A Nebeský, Ladislav
%T The induced paths in a connected graph and a ternary relation determined by them
%J Mathematica Bohemica
%D 2002
%P 397-408
%V 127
%N 3
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2002.134072/
%R 10.21136/MB.2002.134072
%G en
%F 10_21136_MB_2002_134072
Nebeský, Ladislav. The induced paths in a connected graph and a ternary relation determined by them. Mathematica Bohemica, Tome 127 (2002) no. 3, pp. 397-408. doi: 10.21136/MB.2002.134072

[1] M. Changat, S. Klavžar, H. M. Mulder: The all-path transit function of a graph. Czechoslovak Math. J. 52 (2001), 439–448. | MR

[2] G. Chartrand, L. Lesniak: Graphs & Digraphs. Third edition. Chapman & Hall, London, 1996. | MR

[3] P. Duchet: Convex sets in graphs, II. Minimal path convexity. J. Combinatorial Theory, Series B 44 (1998), 307–316. | MR

[4] H-D. Ebbinghaus, J. Flum: Finite Model Theory. Springer, Berlin, 1995. | MR

[5] M. A. Morgana, H. M. Mulder: The induced path convexity, betweenness and svelte graphs. (to appear). | MR

[6] H. M. Mulder: The interval function of a graph. MC-tract 132, Mathematisch Centrum, Amsterdam, 1980. | MR | Zbl

[7] H. M. Mulder: Transit functions on graphs. In preparation. | Zbl

[8] L. Nebeský: A characterization of the interval function of a connected graph. Czechoslovak Math. J. 44 (1994), 173–178. | MR

[9] L. Nebeský: Geodesics and steps in a connected graph. Czechoslovak Math. J. 47 (1997), 149–161. | DOI | MR

[10] L. Nebeský: Characterizing the interval function of a connected graph. Math. Bohem. 123 (1998), 137–144. | MR

[11] L. Nebeský: A theorem for an axiomatic approach to metric properties of connected graphs. Czechoslovak Math. J. 50 (2000), 121–133. | DOI | MR

[12] L. Nebeský: The interval function of a connected graph and a characterization of geodetic graphs. Math. Bohem. 126 (2001), 247–254. | MR | Zbl

Cité par Sources :