The induced paths in a connected graph and a ternary relation determined by them

Nebeský, Ladislav. "The induced paths in a connected graph and a ternary relation determined by them." Mathematica Bohemica 127.3 (2002): 397-408. <http://eudml.org/doc/249053>.

@article{Nebeský2002,
abstract = {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 $.},
author = {Nebeský, Ladislav},
journal = {Mathematica Bohemica},
keywords = {connected graph; induced path; ternary relation; finite structure; connected graph; induced path; ternary relation; finite structure},
language = {eng},
number = {3},
pages = {397-408},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {The induced paths in a connected graph and a ternary relation determined by them},
url = {http://eudml.org/doc/249053},
volume = {127},
year = {2002},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 127
IS - 3
SP - 397
EP - 408
AB - 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 $.
LA - eng
KW - connected graph; induced path; ternary relation; finite structure; connected graph; induced path; ternary relation; finite structure
UR - http://eudml.org/doc/249053
ER -