On signpost systems and connected graphs

Nebeský, Ladislav. "On signpost systems and connected graphs." Czechoslovak Mathematical Journal 55.2 (2005): 283-293. <http://eudml.org/doc/30945>.

@article{Nebeský2005,
abstract = {By a signpost system we mean an ordered pair $(W, P)$, where $W$ is a finite nonempty set, $P \subseteq W \times W \times W$ and the following statements hold: \[ \text\{if \} (u, v, w) \in P, \text\{ then \} (v, u, u) \in P\text\{ and \} (v, u, w) \notin P,\text\{ for all \}u, v, w \in W; \text\{ if \} u \ne v,i \text\{ then there exists \} r \in W \text\{ such that \} (u, r, v) \in P,\text\{ for all \} u, v \in W. \] We say that a signpost system $(W, P)$ is smooth if the folowing statement holds for all $u, v, x, y, z \in W$: if $(u, v, x), (u, v, z), (x, y, z) \in P$, then $(u, v, y) \in P$. We say thay a signpost system $(W, P)$ is simple if the following statement holds for all $u, v, x, y \in W$: if $(u, v, x), (x, y, v) \in P$, then $(u, v, y), (x, y, u) \in P$. By the underlying graph of a signpost system $(W, P)$ we mean the graph $G$ with $V(G) = W$ and such that the following statement holds for all distinct $u, v \in W$: $u$ and $v$ are adjacent in $G$ if and only if $(u,v, v) \in P$. The main result of this paper is as follows: If $G$ is a graph, then the following three statements are equivalent: $G$ is connected; $G$ is the underlying graph of a simple smooth signpost system; $G$ is the underlying graph of a smooth signpost system.},
author = {Nebeský, Ladislav},
journal = {Czechoslovak Mathematical Journal},
keywords = {connected graph; signpost system; connected graph; signpost system},
language = {eng},
number = {2},
pages = {283-293},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On signpost systems and connected graphs},
url = {http://eudml.org/doc/30945},
volume = {55},
year = {2005},
}

TY - JOUR
AU - Nebeský, Ladislav
TI - On signpost systems and connected graphs
JO - Czechoslovak Mathematical Journal
PY - 2005
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 55
IS - 2
SP - 283
EP - 293
AB - By a signpost system we mean an ordered pair $(W, P)$, where $W$ is a finite nonempty set, $P \subseteq W \times W \times W$ and the following statements hold: \[ \text{if } (u, v, w) \in P, \text{ then } (v, u, u) \in P\text{ and } (v, u, w) \notin P,\text{ for all }u, v, w \in W; \text{ if } u \ne v,i \text{ then there exists } r \in W \text{ such that } (u, r, v) \in P,\text{ for all } u, v \in W. \] We say that a signpost system $(W, P)$ is smooth if the folowing statement holds for all $u, v, x, y, z \in W$: if $(u, v, x), (u, v, z), (x, y, z) \in P$, then $(u, v, y) \in P$. We say thay a signpost system $(W, P)$ is simple if the following statement holds for all $u, v, x, y \in W$: if $(u, v, x), (x, y, v) \in P$, then $(u, v, y), (x, y, u) \in P$. By the underlying graph of a signpost system $(W, P)$ we mean the graph $G$ with $V(G) = W$ and such that the following statement holds for all distinct $u, v \in W$: $u$ and $v$ are adjacent in $G$ if and only if $(u,v, v) \in P$. The main result of this paper is as follows: If $G$ is a graph, then the following three statements are equivalent: $G$ is connected; $G$ is the underlying graph of a simple smooth signpost system; $G$ is the underlying graph of a smooth signpost system.
LA - eng
KW - connected graph; signpost system; connected graph; signpost system
UR - http://eudml.org/doc/30945
ER -