### On the distance function of a connected graph

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.

Skip to main content (access key 's'),
Skip to navigation (access key 'n'),
Accessibility information (access key '0')

Back to Simple Search
# Advanced Search

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.

In [3], the present author used a binary operation as a tool for characterizing geodetic graphs. In this paper a new proof of the main result of the paper cited above is presented. The new proof is shorter and simpler.

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\left(G\right)$ into the set of all positive integers such that $|c\left(x\right)-c\left(y\right)|\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\left(G\right)$. Let $G$ be a connected graph. By the hamiltonian chromatic number of $G$ we mean $$min(max(c\left(z\right);\phantom{\rule{0.166667em}{0ex}}z\in V\left(G\right)\left)\right),$$ 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...

If $G$ is a connected graph with distance function $d$, then by a step in $G$ is meant an ordered triple $(u,x,v)$ of vertices of $G$ such that $d(u,x)=1$ and $d(u,v)=d(x,v)+1$. A characterization of the set of all steps in a connected graph was published by the present author in 1997. In Section 1 of this paper, a new and shorter proof of that characterization is presented. A stronger result for a certain type of connected graphs is proved in Section 2.

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;\phantom{\rule{4.0pt}{0ex}}\text{if}\phantom{\rule{4.0pt}{0ex}}(u*v)*v=u,\phantom{\rule{4.0pt}{0ex}}\text{then}\phantom{\rule{4.0pt}{0ex}}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\left(G\right)=V$ and $$E\left(G\right)=\left\{\right\{u,v\}\phantom{\rule{0.222222em}{0ex}}u,v\in V\phantom{\rule{4.0pt}{0ex}}\text{and}\phantom{\rule{4.0pt}{0ex}}u\ne u*v=v\}.$$ Clearly, every travel groupoid is on exactly one graph. In this paper, some properties of travel groupoids on graphs are studied.

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...

**Page 1**
Next