Czechoslovak Mathematical Journal, Vol. 55, No. 2, pp. 283-293, 2005

# On signpost systems and connected graphs

Univerzita Karlova v Praze, Filozoficka fakulta, nam. J. Palacha 2, 116 38 Praha 1, Czech Republic, e-mail: Ladislav.Nebesky@ff.cuni.cz

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:
\gather\text{if} \enspace(u, v, w) \in P,\enspace\text{then}\enspace(v, u, u) \in P\enspace\text{and}\enspace(v, u, w) \not\in P,\enspace\text{for all}\enspace u, v, w \in W;
\text{if}\enspace u \not= v,\enspace\text{then there exists}\enspace r \in W\enspace\text{such that}\enspace(u, r, v) \in P,\enspace\text{for all}\enspace 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: \item{} $G$ is connected; \item{} $G$ is the underlying graph of a simple smooth signpost system; \item{} $G$ is the underlying graph of a smooth signpost system.

Keywords: connected graph, signpost system

Classification (MSC 2000): 05C38, 05C40, 05C12

Full text available as PDF (smallest), as compressed PostScript (.ps.gz) or as raw PostScript (.ps).