1 - 2 of 2
Number of results to display per page
Search Results
2. The induced paths in a connected graph and a ternary relation determined by them.
- Creator:
- Nebeský, Ladislav
- Format:
- bez média and svazek
- Type:
- model:article and TEXT
- Subject:
- connected graph, induced path, ternary relation, and finite structure
- Language:
- English
- Description:
- By a ternary structure we mean an ordered pair (X0, T0), where X0 is a finite nonempty set and T0 is a ternary relation on X0. By the underlying graph of a ternary structure (X0, T0) we mean the (undirected) graph G with the properties that X0 is its vertex set and distinct vertices u and v of G are adjacent if and only if {x ∈ X0 ; T0(u, x, v)}∪{x ∈ X0 ; T0(v,x,u)} = {u, v}. A ternary structure (X0, T0) is said to be the B-structure of a connected graph G if X0 is the vertex set of G and the following statement holds for all u, x,y ∈ X0: T0(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 (X0, T0) is the B-structure of a connected graph G, then G is the underlying graph of (X0, T0). We will prove that there exists no sentence σ of the first-order logic such that a ternary structure (X0, T0) with a connected underlying graph G is the B-structure of G if and only if (X0, T0) satisfies σ.
- Rights:
- http://creativecommons.org/publicdomain/mark/1.0/ and policy:public