MATHEMATICA BOHEMICA, Vol. 127, No. 3, pp. 397-408 (2002)

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

L. Nebesky, Univerzita Karlova v Praze, Filozoficka fakulta, nam. Jana Palacha 2, 116 38 Praha 1, Czech Republic, e-mail: ladislav.nebesky@ff.cuni.cz

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 $$\{x \in X_0 T_0(u, x, v)\} \cup \{x \in X_0 T_0(v, x, u)\} = \{u, v\}.$$ 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$.

Keywords: connected graph, induced path, ternary relation, finite structure

Classification (MSC2000): 05C38, 03C13

Full text of the article:

[Previous Article] [Next Article] [Contents of this Number]
© 2005 ELibM and FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition