×

The induced paths in a connected graph and a ternary relation determined by them. (English) Zbl 1003.05063

Summary: 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\mid T_0(u, x, v)\} \cup \{x \in X_0\mid 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 prove that there exists no sentence \(\sigma \) of 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 \).

MSC:

05C38 Paths and cycles
03C13 Model theory of finite structures
PDFBibTeX XMLCite
Full Text: EuDML