EUDML

Currently displaying 1 – 20 of 81

Order by Relevance | Title | Year of publication

On the distance function of a connected graph

Ladislav Nebeský — 2008

Czechoslovak Mathematical Journal

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.

New proof of a characterization of geodetic graphs

Ladislav Nebeský — 2002

Czechoslovak Mathematical Journal

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.

A new proof of a characterization of the set of all geodesics in a connected graph

Ladislav Nebeský — 1998

Czechoslovak Mathematical Journal

A theorem for an axiomatic approach to metric properties of graphs

Ladislav Nebeský — 2000

Czechoslovak Mathematical Journal

Geodesics and steps in a connected graph

Ladislav Nebeský — 1997

Czechoslovak Mathematical Journal

The hamiltonian chromatic number of a connected graph without large hamiltonian-connected subgraphs

Ladislav Nebeský — 2006

Czechoslovak Mathematical Journal

If $G$ is a connected graph of order $n \geq 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 $| c (x) - c (y) | \geq 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 \geq 3$ . Assume that there exists a subgraph...

On properties of a graph that depend on its distance function

Ladislav Nebeský — 2004

Czechoslovak Mathematical Journal

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.

Travel groupoids

Ladislav Nebeský — 2006

Czechoslovak Mathematical Journal

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; if (u * v) * v = u, 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) = {{u, v} u, v \in V and u \neq u * v = v} .$ Clearly, every travel groupoid is on exactly one graph. In this paper, some properties of travel groupoids on graphs are studied.

Characterizing the maximum genus of a connected graph

Ladislav Nebeský — 1993

Czechoslovak Mathematical Journal

Signpost systems and spanning trees of graphs

Ladislav Nebeský — 2006

Czechoslovak Mathematical Journal

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