Signpost systems and spanning trees of graphs
- Title:
- Signpost systems and spanning trees of graphs
- Creator:
- Nebeský, Ladislav
- Identifier:
- https://cdk.lib.cas.cz/client/handle/uuid:b001ba78-8f1c-43ae-a4f4-c14f415b2a6f
uuid:b001ba78-8f1c-43ae-a4f4-c14f415b2a6f - Subject:
- signpost system, path, connected graph, tree, and spanning tree
- Type:
- model:article and TEXT
- Format:
- bez média and svazek
- Description:
- By a ternary system we mean an ordered pair $(W, R)$, where $W$ is a finite nonempty set and $R \subseteq W \times W \times W$. By a signpost system we mean a ternary system $(W, R)$ satisfying the following conditions for all $x, y, z \in W$: if $(x, y, z) \in R$, then $(y, x, x) \in R$ and $(y, x, z) \notin R$; if $x \ne y$, then there exists $t \in W$ such that $(x, t, y) \in R$. In this paper, a signpost system is used as a common description of a connected graph and a spanning tree of the graph. By a ct-pair we mean an ordered pair $(G, T)$, where $G$ is a connected graph and $T$ is a spanning tree of $G$. If $(G, T)$ is a ct-pair, then by the guide to $(G,T)$ we mean the ternary system $(W, R)$, where $W = V(G)$ and the following condition holds for all $u, v, w \in W$: $(u, v, w) \in R$ if and only if $uv \in E(G)$ and $v$ belongs to the $u-w$ path in $T$. By Proposition 1, the guide to a ct-pair is a signpost system. We say that a signpost system is tree-controlled if it satisfies a certain set of four axioms (these axioms could be formulated in a language of the first-order logic). Consider the mapping $\phi $ from the class of all ct-pairs into the class of all signpost systems such that $\phi ((G, T))$ is the guide to $(G, T)$ for every ct-pair $(G, T)$. It is proved in this paper that $\phi $ is a bijective mapping from the class of all ct-pairs onto the class of all tree-controlled signpost systems.
- Language:
- English
- Rights:
- http://creativecommons.org/publicdomain/mark/1.0/
policy:public - Coverage:
- 885-893
- Source:
- Czechoslovak Mathematical Journal | 2006 Volume:56 | Number:3
- Harvested from:
- CDK
- Metadata only:
- false
The item or associated files might be "in copyright"; review the provided rights metadata:
- http://creativecommons.org/publicdomain/mark/1.0/
- policy:public