| Title:
|
Signpost systems and spanning trees of graphs (English) |
| Author:
|
Nebeský, Ladislav |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
56 |
| Issue:
|
3 |
| Year:
|
2006 |
| Pages:
|
885-893 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
By a ternary system we mean an ordered pair $(W, R)$, where $W$ is a finite nonempty set and $R \subseteq W \times W \times W$. By a signpost system we mean a ternary system $(W, R)$ satisfying the following conditions for all $x, y, z \in W$: if $(x, y, z) \in R$, then $(y, x, x) \in R$ and $(y, x, z) \notin R$; if $x \ne y$, then there exists $t \in W$ such that $(x, t, y) \in R$. In this paper, a signpost system is used as a common description of a connected graph and a spanning tree of the graph. By a ct-pair we mean an ordered pair $(G, T)$, where $G$ is a connected graph and $T$ is a spanning tree of $G$. If $(G, T)$ is a ct-pair, then by the guide to $(G,T)$ we mean the ternary system $(W, R)$, where $W = V(G)$ and the following condition holds for all $u, v, w \in W$: $(u, v, w) \in R$ if and only if $uv \in E(G)$ and $v$ belongs to the $u-w$ path in $T$. By Proposition 1, the guide to a ct-pair is a signpost system. We say that a signpost system is tree-controlled if it satisfies a certain set of four axioms (these axioms could be formulated in a language of the first-order logic). Consider the mapping $\phi $ from the class of all ct-pairs into the class of all signpost systems such that $\phi ((G, T))$ is the guide to $(G, T)$ for every ct-pair $(G, T)$. It is proved in this paper that $\phi $ is a bijective mapping from the class of all ct-pairs onto the class of all tree-controlled signpost systems. (English) |
| Keyword:
|
signpost system |
| Keyword:
|
path |
| Keyword:
|
connected graph |
| Keyword:
|
tree |
| Keyword:
|
spanning tree |
| MSC:
|
05C05 |
| MSC:
|
05C12 |
| MSC:
|
05C38 |
| MSC:
|
05C99 |
| MSC:
|
90B10 |
| idZBL:
|
Zbl 1164.05392 |
| idMR:
|
MR2261660 |
| . |
| Date available:
|
2009-09-24T11:39:05Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/128113 |
| . |
| Reference:
|
[1] G. Chartrand, L. Lesniak: Graphs & Digraphs. Third edition.Chapman & Hall, London, 1996. MR 1408678 |
| Reference:
|
[2] H. M. Mulder, 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 tree as a finite nonempty set with a binary operation.Mathematica Bohemica 125 (2000), 455–458. MR 1802293 |
| 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 |
| Reference:
|
[7] L. Nebeský: Signpost systems and connected graphs.Czechoslovak Math. J. 55(130) (2005), 283–293. MR 2137138, 10.1007/s10587-005-0022-0 |
| . |
