Article
| Title: | On signpost systems and connected graphs (English) |
| Author: | Nebeský, Ladislav |
| Language: | English |
| Journal: | Czechoslovak Mathematical Journal |
| ISSN: | 0011-4642 (print) |
| ISSN: | 1572-9141 (online) |
| Volume: | 55 |
| Issue: | 2 |
| Year: | 2005 |
| Pages: | 283-293 |
| Summary lang: | English |
| . | |
| Category: | math |
| . | |
| 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. (English) |
| Keyword: | connected graph |
| Keyword: | signpost system |
| MSC: | 05C12 |
| MSC: | 05C38 |
| MSC: | 05C40 |
| idZBL: | Zbl 1081.05054 |
| idMR: | MR2137138 |
| . | |
| Date available: | 2009-09-24T11:23:00Z |
| Last updated: | 2020-07-03 |
| Stable URL: | http://hdl.handle.net/10338.dmlcz/127978 |
| . | |
| Reference: | [1] H. M. Mulder: The Interval Function of a Graph. Math. Centre Tracts 132.Math. Centre, Amsterdam, 1980. MR 0605838 |
| Reference: | [2] H. M. Mulder and L. Nebeský: Modular and median signpost systems and their underlying graphs.Discussiones Mathematicae Graph Theory 23 (2003), 309–324. MR 2070159, 10.7151/dmgt.1204 |
| Reference: | [3] L. Nebeský: Geodesics and steps in a connected graph.Czechoslovak Math. J. 47(122) (1997), 149–161. MR 1435613, 10.1023/A:1022404624515 |
| Reference: | [4] L. Nebeský: An axiomatic approach to metric properties of connected graphs.Czechoslovak Math. J. 50(125) (2000), 3–14. MR 1745453, 10.1023/A:1022472700080 |
| Reference: | [5] L. Nebeský: A theorem for an axiomatic aproach to metric properties of graphs.Czechoslovak Math. J. 50(125) (2000), 121–133. MR 1745467, 10.1023/A:1022401506441 |
| Reference: | [6] L. Nebeský: On properties of a graph that depend on its distance function.Czechoslovak Math. J. 54(129) (2004), 445–456. MR 2059265, 10.1023/B:CMAJ.0000042383.98585.97 |
| . |
Files
| Files | Size | Format | View |
|---|---|---|---|
| CzechMathJ_55-2005-2_2.pdf | 314.7Kb | application/pdf |
View/ |
Search
Partner of
