Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
connected graph; signpost system
connected graph; signpost system
Summary:
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.
References:
[1] H. M. Mulder: The Interval Function of a Graph. Math. Centre Tracts 132. Math. Centre, Amsterdam, 1980. MR 0605838
[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 10.7151/dmgt.1204 | MR 2070159
[3] L. Nebeský: Geodesics and steps in a connected graph. Czechoslovak Math. J. 47(122) (1997), 149–161. DOI 10.1023/A:1022404624515 | MR 1435613
[4] L. Nebeský: An axiomatic approach to metric properties of connected graphs. Czechoslovak Math. J. 50(125) (2000), 3–14. DOI 10.1023/A:1022472700080 | MR 1745453
[5] L. Nebeský: A theorem for an axiomatic aproach to metric properties of graphs. Czechoslovak Math. J. 50(125) (2000), 121–133. DOI 10.1023/A:1022401506441 | MR 1745467
[6] L. Nebeský: On properties of a graph that depend on its distance function. Czechoslovak Math. J. 54(129) (2004), 445–456. DOI 10.1023/B:CMAJ.0000042383.98585.97 | MR 2059265
Search
Partner of
