Signpost systems and spanning trees of graphs

Nebeský, Ladislav

Czechoslovak Mathematical Journal, Tome 56 (2006) no. 3, pp. 885-893.

Résumé

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 $\varphi$ from the class of all ct-pairs into the class of all signpost systems such that $\varphi ((G,T))$ is the guide to $(G,T)$ for every ct-pair $(G,T)$. It is proved in this paper that $\varphi$ is a bijective mapping from the class of all ct-pairs onto the class of all tree-controlled signpost systems.

Détail

Classification : 05C05, 05C12, 05C38, 05C99, 90B10
Mots-clés : signpost system; path; connected graph; tree; spanning tree