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

Title:

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

Creator:

Nebeský, Ladislav

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:53d989f6-56ab-4a1c-ad6d-258b8c02dbbb
uuid:53d989f6-56ab-4a1c-ad6d-258b8c02dbbb
doi:10.21136/MB.2002.134072

Subject:

connected graph, induced path, ternary relation, and finite structure

Type:

model:article and TEXT

Format:

bez média and svazek

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 σ.

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

397-408

Source:

Mathematica bohemica | 2002 Volume:127 | Number:3

Harvested from:

CDK

Metadata only:

false