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.
An axiomatic characterization of the distance function of a connected graph is given in this note. The triangle inequality is not contained in this characterization.
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.
By a ternary structure we mean an ordered pair $(U_0, T_0)$, where $U_0$ is a finite nonempty set and $T_0$ is a ternary relation on $U_0$. A ternary structure $(U_0, T_0)$ is called here a directed geodetic structure if there exists a strong digraph $D$ with the properties that $V(D) = U_0$ and \[ T_0(u, v, w)\quad \text{if} \text{and} \text{only} \text{if}\quad d_D(u, v) + d_D(v, w) = d_D(u, w) \] for all $u, v, w \in U_0$, where $d_D$ denotes the (directed) distance function in $D$. It is proved in this paper that there exists no sentence ${\mathbf s}$ of the language of the first-order logic such that a ternary structure is a directed geodetic structure if and only if it satisfies ${\mathbf s}$.
If $G$ is a connected graph of order $n \ge 1$, then by a hamiltonian coloring of $G$ we mean a mapping $c$ of $V(G)$ into the set of all positive integers such that $\vert c(x) - c(y)\vert \ge n - 1 - D_{G}(x, y)$ (where $D_{G}(x, y)$ denotes the length of a longest $x-y$ path in $G$) for all distinct $x, y \in V(G)$. Let $G$ be a connected graph. By the hamiltonian chromatic number of $G$ we mean \[ \min (\max (c(z);\, z \in V(G))), \] where the minimum is taken over all hamiltonian colorings $c$ of $G$. The main result of this paper can be formulated as follows: Let $G$ be a connected graph of order $n \ge 3$. Assume that there exists a subgraph $F$ of $G$ such that $F$ is a hamiltonian-connected graph of order $i$, where $2 \le i \le \frac{1}{2}(n + 1)$. Then $\mathop {\mathrm hc}(G) \le (n - 2)^2 + 1 - 2(i - 1)(i - 2)$.
By a ternary structure we mean an ordered pair (X0, T0), where X0 is a finite nonempty set and T0 is a ternary relation on X0. By the underlying graph of a ternary structure (X0, T0) we mean the (undirected) graph G with the properties that X0 is its vertex set and distinct vertices u and v of G are adjacent if and only if {x ∈ X0 ; T0(u, x, v)}∪{x ∈ X0 ; T0(v,x,u)} = {u, v}. A ternary structure (X0, T0) is said to be the B-structure of a connected graph G if X0 is the vertex set of G and the following statement holds for all u, x,y ∈ X0: T0(x, u, y) if and only if u belongs to an induced x − y path in G. It is clear that if a ternary structure (X0, T0) is the B-structure of a connected graph G, then G is the underlying graph of (X0, T0). We will prove that there exists no sentence σ of the first-order logic such that a ternary structure (X0, T0) with a connected underlying graph G is the B-structure of G if and only if (X0, T0) satisfies σ.
The interval function (in the sense of H. M. Mulder) is an important tool for studying those properties of a connected graph that depend on the distance between vertices. An axiomatic characterization of the interval function of a connected graph was published by Nebeský in 1994. In Section 2 of the present paper, a simpler and shorter proof of that characterization will be given. In Section 3, a characterization of geodetic graphs will be established; this characterization will utilize properties of the interval function.
In this paper, by a travel groupoid is meant an ordered pair $(V, *)$ such that $V$ is a nonempty set and $*$ is a binary operation on $V$ satisfying the following two conditions for all $u, v \in V$: \[ (u * v) * u = u; \text{ if }(u * v ) * v = u, \text{ then } u = v. \] Let $(V, *)$ be a travel groupoid. It is easy to show that if $x, y \in V$, then $x * y = y$ if and only if $y * x = x$. We say that $(V, *)$ is on a (finite or infinite) graph $G$ if $V(G) = V$ and \[ E(G) = \lbrace \lbrace u, v\rbrace \: u, v \in V \text{ and } u \ne u * v = v\rbrace . \] Clearly, every travel groupoid is on exactly one graph. In this paper, some properties of travel groupoids on graphs are studied.