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

Access to the full text of journal articles on this site is restricted to the subscribers of Myris Trade. To activate your access, please contact Myris Trade at myris@myris.cz.
Subscribers of Springer need to access the articles on their site, which is http://www.springeronline.com/10587.