Geodesic
On signpost systems and connected graphs
Czechoslovak Mathematical Journal, Tome 55 (2005) no. 2, pp. 283-293
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 05C12, 05C38, 05C40
Keywords: connected graph; signpost system 
@article{CMJ_2005_55_2_a1,
     author = {Nebesk\'y, Ladislav},
     title = {On signpost systems and connected graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {283--293},
     year = {2005},
     volume = {55},
     number = {2},
     mrnumber = {2137138},
     zbl = {1081.05054},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2005_55_2_a1/}
}
TY  - JOUR
AU  - Nebeský, Ladislav
TI  - On signpost systems and connected graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2005
SP  - 283
EP  - 293
VL  - 55
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/CMJ_2005_55_2_a1/
LA  - en
ID  - CMJ_2005_55_2_a1
ER  - 
%0 Journal Article
%A Nebeský, Ladislav
%T On signpost systems and connected graphs
%J Czechoslovak Mathematical Journal
%D 2005
%P 283-293
%V 55
%N 2
%U http://geodesic.mathdoc.fr/item/CMJ_2005_55_2_a1/
%G en
%F CMJ_2005_55_2_a1
Nebeský, Ladislav. On signpost systems and connected graphs. Czechoslovak Mathematical Journal, Tome 55 (2005) no. 2, pp. 283-293. http://geodesic.mathdoc.fr/item/CMJ_2005_55_2_a1/

[1] H. M. Mulder: The Interval Function of a Graph. Math. Centre Tracts 132. Math. Centre, Amsterdam, 1980. | MR

[2] H. M. Mulder and L. Nebeský: Modular and median signpost systems and their underlying graphs. Discussiones Mathematicae Graph Theory 23 (2003), 309–324. | DOI | MR

[3] L. Nebeský: Geodesics and steps in a connected graph. Czechoslovak Math.  J. 47(122) (1997), 149–161. | DOI | MR

[4] L. Nebeský: An axiomatic approach to metric properties of connected graphs. Czechoslovak Math.  J. 50(125) (2000), 3–14. | DOI | MR

[5] L. Nebeský: A theorem for an axiomatic aproach to metric properties of graphs. Czechoslovak Math.  J. 50(125) (2000), 121–133. | DOI | MR

[6] L. Nebeský: On properties of a graph that depend on its distance function. Czechoslovak Math.  J. 54(129) (2004), 445–456. | DOI | MR