By the interval function of a finite connected graph we mean the interval function in the sense of H. M. Mulder. This function is very important for studying properties of a finite connected graph which depend on the distance between vertices. The interval function of a finite connected graph was characterized by the present author. The interval function of an infinite connected graph can be defined similarly to that of a finite one. In the present paper we give a characterization of the interval function of each connected graph.
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(G) = W$ onto the set of all ternary systems $(W, T)$ satisfying the axioms (A1)–(A5) is found in this paper.
A (finite) acyclic connected graph is called a tree. Let W be a finite nonempty set, and let H(W) be the set of all trees T with the property that W is the vertex set of T. We will find a one-to-one correspondence between H(W) and the set of all binary operations on W which satisfy a certain set of three axioms (stated in this note).
We say that a binary operation $*$ is associated with a (finite undirected) graph $G$ (without loops and multiple edges) if $*$ is defined on $V(G)$ and $uv\in E(G)$ if and only if $u\ne v$, $u * v=v$ and $v*u=u$ for any $u$, $v\in V(G)$. 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 hamiltonian coloring of a connected graph G of order n ≥ 1 we mean a mapping c of V (G) into the set of all positive integers such that |c(x) − c(y)| ≥ n − 1 − DG(x, y) (where DG(x, y) denotes the length of a longest x − y path in G) for all distinct x, y ∈ G. In this paper we study hamiltonian colorings of non-hamiltonian connected graphs with long cycles, mainly of connected graphs of order n ≥ 5 with circumference n − 2.
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 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.