We say that a binary operation $*$ is associated with a (finite undirected) graph $G$ (without loops and multiple edges) if $*$ is defined on $V\left(G\right)$ and $uv\in E\left(G\right)$ if and only if $u\ne v$, $u*v=v$ and $v*u=u$ for any $u$, $v\in V\left(G\right)$. In the paper it is proved that a connected graph $G$ is geodetic if and only if there exists a binary operation associated with $G$ which fulfils a certain set of four axioms. (This characterization is obtained as an immediate consequence of a stronger result proved in the paper).

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

By a chordal graph is meant a graph with no induced cycle of length $\ge 4$. By a ternary system is meant an ordered pair $(W,T)$, where $W$ is a finite nonempty set, and $T\subseteq W\times W\times W$. Ternary systems satisfying certain axioms (A1)–(A5) are studied in this paper; note that these axioms can be formulated in a language of the first-order logic. For every finite nonempty set $W$, a bijective mapping from the set of all connected chordal graphs $G$ with $V\left(G\right)=W$ onto the set of all ternary systems $(W,T)$ satisfying the axioms (A1)–(A5)...

Let $\alpha \left(n\right)$ be the least number $k$ for which there exists a simple graph with $k$ vertices having precisely $n\ge 3$ spanning trees. Similarly, define $\beta \left(n\right)$ as the least number $k$ for which there exists a simple graph with $k$ edges having precisely $n\ge 3$ spanning trees. As an $n$-cycle has exactly $n$ spanning trees, it follows that $\alpha \left(n\right),\beta \left(n\right)\le n$. In this paper, we show that $\alpha \left(n\right)\le \frac{1}{3}(n+4)$ and $\beta \left(n\right)\le \frac{1}{3}(n+7)$ if and only if $n\notin \{3,4,5,6,7,9,10,13,18,22\}$, which is a subset of Euler’s idoneal numbers. Moreover, if $n\neg \equiv 2(mod3)$ and $n\ne 25$ we show that $\alpha \left(n\right)\le \frac{1}{4}(n+9)$ and $\beta \left(n\right)\le \frac{1}{4}(n+13).$ This improves some previously estabilished...

For a connected graph $G$ of order $n\ge 3$ and an ordering $s{v}_1$, $v_2,\cdots ,v_n$ of the vertices of $G$, $d\left(s\right)={\sum }_{i=1}^{n-1}d(v_i,v_{i+1})$, where $d(v_i,v_{i+1})$ is the distance between $v_i$ and $v_{i+1}$. The traceable number $t\left(G\right)$ of $G$ is defined by $t\left(G\right)=min\left\}d\left(s\right)\right\{,$ where the minimum is taken over all sequences $s$ of the elements of $V\left(G\right)$. It is shown that if $G$ is a nontrivial connected graph of order $n$ such that $l$ is the length of a longest path in $G$ and $p$ is the maximum size of a spanning linear forest in $G$, then $2n-2-p\le t\left(G\right)\le 2n-2-l$ and both these bounds are sharp. We establish a formula for the traceable...