| Title:
|
The induced paths in a connected graph and a ternary relation determined by them (English) |
| Author:
|
Nebeský, Ladislav |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
127 |
| Issue:
|
3 |
| Year:
|
2002 |
| Pages:
|
397-408 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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 \[\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 $. (English) |
| Keyword:
|
connected graph |
| Keyword:
|
induced path |
| Keyword:
|
ternary relation |
| Keyword:
|
finite structure |
| MSC:
|
03C13 |
| MSC:
|
05C38 |
| idZBL:
|
Zbl 1003.05063 |
| idMR:
|
MR1931324 |
| DOI:
|
10.21136/MB.2002.134072 |
| . |
| Date available:
|
2009-09-24T22:02:51Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/134072 |
| . |
| Reference:
|
[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 1844322 |
| Reference:
|
[2] G. Chartrand, L. Lesniak: Graphs & Digraphs. Third edition.Chapman & Hall, London, 1996. MR 1408678 |
| Reference:
|
[3] P. Duchet: Convex sets in graphs, II. Minimal path convexity.J. Combinatorial Theory, Series B 44 (1998), 307–316. MR 0941439 |
| Reference:
|
[4] H-D. Ebbinghaus, J. Flum: Finite Model Theory.Springer, Berlin, 1995. MR 1409813 |
| Reference:
|
[5] M. A. Morgana, H. M. Mulder: The induced path convexity, betweenness and svelte graphs.(to appear). MR 1910118 |
| Reference:
|
[6] H. M. Mulder: The interval function of a graph.MC-tract 132, Mathematisch Centrum, Amsterdam, 1980. Zbl 0446.05039, MR 0605838 |
| Reference:
|
[7] H. M. Mulder: Transit functions on graphs.In preparation. Zbl 1166.05019 |
| Reference:
|
[8] L. Nebeský: A characterization of the interval function of a connected graph.Czechoslovak Math. J. 44 (1994), 173–178. MR 1257943 |
| Reference:
|
[9] L. Nebeský: Geodesics and steps in a connected graph.Czechoslovak Math. J. 47 (1997), 149–161. MR 1435613, 10.1023/A:1022404624515 |
| Reference:
|
[10] L. Nebeský: Characterizing the interval function of a connected graph.Math. Bohem. 123 (1998), 137–144. MR 1673965 |
| Reference:
|
[11] L. Nebeský: A theorem for an axiomatic approach to metric properties of connected graphs.Czechoslovak Math. J. 50 (2000), 121–133. MR 1745467, 10.1023/A:1022401506441 |
| Reference:
|
[12] L. Nebeský: The interval function of a connected graph and a characterization of geodetic graphs.Math. Bohem. 126 (2001), 247–254. Zbl 0977.05045, MR 1826487 |
| . |
