\documentstyle[twoside,lot,12pt]{article}

\def\theaddresshead{Address of the author}
\evensidemargin 11mm 
\oddsidemargin  11mm
\marginparwidth 0pt
\marginparsep 0pt

\topmargin -1in
\headheight 0.7cm
\headsep 1.8cm
\footheight 0.7cm
\footskip 2cm
\textheight 22cm
\textwidth 14cm 

\marginparpush 0pt

\startpage{1}
\pubnr{[B33l]}
\semnr{33^e}
\parindent 20pt
\topmargin-1.cm

\newcommand{\qed}{\hfill \rule{0.7ex}{1.5ex}}

\begin{document}
\titlepagestyle{empty}
\thispagestyle{headings}

%\title{Hamiltonicity exponent of digraphs}
%\author{G\"unter Schaar}
\title{Hamiltonicity exponent of digraphs}
\author[G.~Schaar]{G\"unter Schaar\\
Fakult\"at f\"ur Mathematik und Informatik\\
TU Bergakademie Freiberg}
\date{}
\maketitle
%\rule{\textwidth}{0.1mm}
%\pagestyle{empty}
{\bf 0.}\quad Initiated by Sekanina [6], in the sixties and more intensively 
in the seventies there were considered powers of undirected graphs with
special respect to their Hamiltonian behaviour. These investigations have 
resulted in a lot of interesting and partly very profound propositions;
we only remind of the (simple) result of Sekanina [6] that the cube of every
finite connected graph is Hamiltonian connected, or of the famous theorem
of Fleischner [1] that the square of any nontrivial block is Hamiltonian.
For directed graphs (digraphs), the situation is 
completely different; till not long ago nobody was seriously engaged in
studying the analogous problem for digraphs (see [4]). The main reason
for this situation is that for digraphs, these questions become much more
complicated than in the undirected case. This paper intends to discuss
some of the difficulties arising in the case of digraphs and to present some
beginning results. All digraphs are supposed to be finite.\\[0.4cm]
{\bf 1.} Let $G = (V,E)$ be a simple digraph with vertex set $V(G) = V$
and edge set $E(G) = E$; then every (directed) edge can be written as an
ordered pair of uniquely determined different vertices, and (directed)
paths and (directed) cycles are denoted by the associated sequences of
their vertices. Now, such properties of $G$ as to be {\it traceable, 
Hamiltonian, $r$-Hamiltonian $(r = 1,2,...)$, Hamiltonian connected} are
defined in the same way as for undirected graphs by taking paths and
cycles as directed ones, and this can also be done regarding the construction
of higher powers of $G$, namely: The $k${\it -th power} $G^k$ of $G$ is the
digraph $G^k = (V_k,E_k)$ with
\begin{eqnarray*}
V_k := V \mbox{ and } E_k :=\{(x,y) : x,y \in V \wedge 1\le d_G(x,y)\le k\},
\end{eqnarray*}
$k = 1,2,...,$ where $d_G(x,y)$ denotes the distance from $x$ to $y$
 in $G$, that is the length of a shortest path from $x$ to $y$ in $G$ if
there is any and $\infty $ otherwise.\\[0.2cm]
In spite of these analogous definitions the Hamiltonian properties of powers
of undirected and directed graphs are essentially different. A first 
difference is rather evident: For an undirected connected graph $G$ on 
$n\ge 3$ vertices, $G^3$ is Hamiltonian. For a connected digraph $G$, however,
it may happen that $d_G(x,y) = \infty $ for some $x,y\in V$; then it follows 
that $d_{G^k}(x,y) = \infty $ for every $k = 1,2,...,$ and no power $G^k$
can become a Hamiltonian digraph. Therefore, if we want to improve the 
Hamiltonian behaviour of a digraph $G$ by raising $G$ to higher powers and
to obtain Hamiltonicity we have to suppose $G$ to be {\it strongly connected}.
Notwithstanding, even under this suppositon it is not valid that $G^3$
(or any other power $G^k$) is Hamiltonian for every such $G$, but it holds:\\[0.4cm]
{\it For every $k\ge 1$ and every $n\ge 2k + 4$ there is a strongly connected 
digraph $G$ on $n$ vertices such that $G^k$ is not traceable.}\\[0.4cm]
For the proof, we consider the digraph $G$ consisting of the path
$(x_0,x_1,...,x_r,y_0)$ with $r\ge k$ and of the $t$ paths 
$(y_0,y_i,x_0), i = 1,...,t$, with $t\ge k+2$; obviously, $G$ is a strongly
connected digraph on $r + t + 2 \ge 2k + 4$ vertices and $G^k$ does not 
contain any Hamiltonian path.\\
This fact makes clear that for digraphs, we cannot expect to get results 
being satisfactory or simple in a similar way as for undirected graphs. 
On the other hand, for every strongly connected digraph $G$ there is a $k$ 
such that $G^k$ is the complete digraph and therefore, has the Hamiltonian
properties mentioned above. Thus it is sensible to define the following 
invariants for strongly connected digraphs $G:$\\
The {\it Hamiltonicity exponent} $e_H(G)$ by
\begin{eqnarray*} 
e_H(G) :=  min \{ k\ge 1 : G^k \mbox { is Hamiltonian \}  (if}\quad |V|\ge 2),
\end{eqnarray*}
and analogously, the {\it traceability exponent} $e_T(G)$, the 
$r${\it -Hamiltonicity exponent} $e_{r-H}(G), r = 1,...,|V|-2$, and
the {\it Hamiltonian connectedness exponent} $e_{HC}(G)$.\\
Clearly, $e_T(G) \le e_H(G)\le e_{HC}(G)\le |V| - 1$ and $e_{r-H}(G) \le |V| - 1$,
i.e. we have trivial upper bounds for these invariants. Now a first task will
be to find nontrivial upper bounds for these exponents, and animated by the
satisfactory results for powers of undirected graphs we are especially
interested in such upper bounds not depending on the vertex number. We have
just seen that the latter kind of bounds does not exist for the whole class
of all strongly connected digraphs, and therefore, we have to look for suitable
subclasses. A very simple subclass - and the only one having been studied in 
this connection hitherto - is the class of directed cacti. Before changing
over into considering such cacti besides, we point out to the following
fact:\\
For the strong connectivity $c_s(G)$ of a digraph $G$ it holds (cf. [4])
\begin{eqnarray*}
c_s(G^k)\ge  min (k c_s(G), |V| - 1),\quad k = 1,2,...;
\end{eqnarray*}
in view of this formula it may be expected that the strong connectivity of $G$ 
will have effects also on the Hamiltonian properties of higher powers of $G$.
As an example for first results in this direction we mention that
\begin{eqnarray*}
e_H(G) \le  \left\lceil\frac{|V|}{2r}\right\rceil
\end{eqnarray*}
can be proved (cf. [7]) for every strongly $r$-connected digraph $G$ with
$|V|\ge 2, r \ge 1$.\\[0.4cm]
{\bf 2.}\quad A {\it directed cactus (}or {\it dicactus)} is defined to be a
strongly connected finite simple digraph $G$ every edge of which is contained 
in at most one (and therefore, in exactly one) cycle in $G$. Among the 
properties of dicacti we emphasize the following one which is important for
the proofs of our main results.\\[0.4cm]
{\bf Lemma 2.1:} {\it For every (directed) cycle $c$ in a dicactus $G$, after
deleting the edges of $c$ each component of the resulting digraph $G'$ contains
exactly one vertex in common with $c$ and is $a$ (possibly trivial) dicactus
itself.}\\[0.4cm]
P r o o f: Let $H$ be a component of $G', x \in V(c)\cap V(H)$ and
$e' = (x',x) \in E(c), e" = (x,x")\in E(c)$. Consider a maximal strongly connected 
subgraph $H'$ of $H$ with $x\in V(H')$. Then $H'$ cannot contain any $y\in V(c)$
with $y\not= x$, because otherwise there would be an $x,y$-path in $H'$ and
therefore, a cycle $c'\not= c$ in $G$ containing $e'$.\\
Assume $H'\not= H$; then there is an edge $(a',a)\in E(H)$ with $a'\in V(H'),
a\notin V(H')$ or an edge $(b,b')\in E(H)$ with $b'\in V(H'), b\not\in V(H')$, and in $G$
there exists a path $p$ from $a$ to $x$ (resp., from $x$ to $b$). Assume that
not all edges of $p$ belong to $H$, and let $e_1 = (y,z)$ be the first
(resp., $e_1 = (z,y)$ the last) edge on $p$ not belonging to $H$. Then
$e_1\in E(c)$, and $y,z\in V(c)$ and $y\not= x$. Further we have a subpath 
$p'$ of $p$ in $H$ with $p' = (a,...,y)$ (resp., $p' = (y,...,b))$ and
therefore, a path $p_1 = (x,...,a', a,...,y)$ 
(resp., $p_1 = (y,...,b, b',...,x))$ in $H$ because $H'$ is strongly connected.
Hence it follows that there exists a cycle $c'\not= c$ in $G$ containing
$e'$ (resp., a cycle $c"\not= c$ in $G$ containing $e"$); this is a 
contradiction in either case.\\
Thus, $p$ is a path in $H$, and the digraph $H'\cup p\cup e^*$ with
$e^* = (a',a)$ (resp., $e^* = (b,b')$) is a strongly connected subgraph of $H$
containing $x$, in contradiction to the maximality of $H'$. This yields $H' = H$, 
and the asserted properties of $H$ are proved.$\Box$ \\
Using Lemma 2.1 and induction to the number of cycles in $G$ we can prove
(cf. [4])\\[0.4cm]
{\bf Lemma 2.2:} {\it Let $G$ be a dicactus; then for every $e = (x,y)\in E(G)$
there is a Hamiltonian path $h = (y,y',...,x',x)$ in $G^3$ with
$d_G(y,y'), d_G(x',x)\in \{ 1,2\}$ }.\\[0.2cm]
As immediate consequences of Lemma 2.2 we obtain\\[0.4cm]
{\bf Corollary 2.3} (cf. [4]): {\it For every dicactus $G$ on at least two
vertices, $e_H(G)\le 3$},\\[0.4cm]
{\bf Corollary 2.4} (cf. [5]): {\it For every dicactus $G$ on at least three
vertices, $e_{1-H}(G)\le 3$}.\\[0.4cm]
Lemma 2.2 is also an important tool for proving the following statement
which improves Corollary 2.3.\\[0.4cm]
{\bf Theorem 2.5} (cf.[4]): {\it For every dicactus $G, e_{HC}(G)\le 3$}.\\[0.4cm]
Obviously, the upper bound 3 is best possible in Corollary 2.3 and therefore,
in Corollary 2.4 and Theorem 2.5. (It is sufficient to take the dicactus
arising from an undirected 3-star by replacing at first every edge by an
undirected path of length 2 and then every edge by a directed cycle of
length 2.)\\[0.4cm]
{\bf 3.}\quad The results just mentioned give rise to the question which
subclasses of dicacti have a Hamiltonian (or 1-Hamiltonian or Hamiltonian
connected) square. For this end we consider dicacti with the following 
property:\\
A dicactus $G$ is said to fulfil the {\it 2-degree-condition} iff every
cycle in $G$ contains a vertex of degreee (= valency) 2 in $G$  
(i.e. a vertex $x$ with $v(x : G) = v^+(x : G) + v^-(x : G) = 2)$.\\
By induction to the number of edges we obtain (cf. [5])\\[0.4cm]
{\bf Lemma 3.1:} {\it For every dicactus $G$ fulfilling the 2-degree-condition
and any edge $e = (x,y)\in E(G)$ there is a Hamiltonian path $h = (y,...,x)$
in $G^2$.}\\[0.2cm]
This yields immediately\\[0.4cm] 
{\bf Corollary 3.2:} {\it For every dicactus G on at least two vertices
fulfilling the 2-degree-condition, $e_H(G)\le 2$.}\\[0.4cm]
However, the suppositions in Corollary 3.2 are not sufficient for $G$ to have 
a 1-Hamiltonian square or a Hamiltonian connected
square; this can be easily seen by simple examples. (For 
instance, let $G_r$ be the cycle $(0,1,...,4r-1, 0)$ of length $4r,\, r = 1,2,...$;
then there is no Hamiltonian path in $G^2_r$ from $0$ to $2r$. Similarly,
for the dicactus $G$ consisting of the three cycles $(x,y,z,x)$, $(y,a,y)$,
$(z,b,z)$, the digraph $G^2-x$ is not Hamiltonian.) By a more detailed proof
exhausting the suppositions on $G$ most accurately one can improve Lemma 3.1
and obtain further statements (cf. [5]); after all, many problems concerning
dicacti with 2-degree-condition remain open.\\[0.4cm]
{\bf 4.}\quad In this final section let us consider dicacti of the simplest 
shape, namely those having at most one cycle of length greater than 2.
If all cycles in G are of length 2 (Case 1) it follows that $G$ is a 
bidirected simple connected digraph without cycles of length $>2$. 
Replacing every cycle of length 2 in $G$ by an undirected edge we get the
associated undirected graph $G_u$ which is obviously a tree. Of course,
if $|V(G)|\ge 3$ (the case $|V(G)| = 2$ is trivial), $G^2$ is Hamiltonian
iff $G^2_u$ is Hamiltonian, and this occurs iff the tree $G_u$ is a
caterpillar, according a result in [2]. Thus, we obtain a simple
characterization of the dicacti of Case 1 satisfying $e_H(G)\le 2$.\\
A dicactus $G$ containing exactly one cycle of length $\ge 3$ (Case 2)
is called a {\it unicyclic dicactus}. Denote (in such a $G$) this cycle by
$c = (x_0,x_1,...,x_l = x_0),\quad l\ge 3,$
and the $l$ components of the digraph $G - E(c)$ by $G_1,...,G_l$ where
$x_j\in V(G_j), j = 1,...,l$. Then every $G_j$ is a dicactus of Case 1, and 
using these denotations we can show (cf.[4]) the following theorem 
characterizing all unicyclic dicacti fulfilling $e_H(G)\le 2.$\\[0.4cm]
{\bf Theorem 4.1:} {\it For a unicyclic dicactus $G$, it holds $e_H(G)\le 2$
iff the following conditions are satisfied:\\
(1) Every undirected graph $(G_j)_u, j = 1,...,l$, is a caterpillar (with
at least 3 vertices), a path of length 1 or a trivial graph (i.e. a point graph);\\
(2) if $(G_j)_u - x_j$ for some $j\in \{1,...,l\}$ has two nontrivial
components then there is an $x_i$ on the cycle $c,\, i\in \{1,...,l\}$,
such that $G_i - x_i$ is empty (i.e. without any vertex) and for every
vertex $x_t\not= x_j, t\in\{1,...,l\}$, belonging to the directed path on 
$c$ from $x_j$ to $x_i$ at most one component of $(G_t)_u - x_t$ is nontrivial;\\
(3) if $(G_j)_u - x_j$ for some $j\in \{1,...,l\}$ has a nontrivial component
then $x_j$ either belongs to the path $g_j$ arising from $(G_j)_u$ by deleting
all vertices of degree 1, or it has degree 1 in $(G_j)_u$ and is a neighbour
of an endvertex of this path $g_j$.}\\[0.2cm]
The sufficiency is proved by construction: Every $(G_j)_u, j = 1,...,l$,
is a caterpillar (possibly degenerated), and we can construct suitable 
Hamiltonian paths in $(G_j)^2_u$ by Neuman's Theorem on trees [3] and so
in $G^2_j$; these paths are composed to a Hamiltonian cycle in $G^2$.
The proof of the necessity is straightforward, indeed, it is rather complicated
in the details.\\
One of the most essential tasks of further investigations on this subject will
be to find other suitable subclasses of strongly connected digraphs and
good upper bounds for their Hamiltonian exponents.\\[0.4cm]
\vfill
\eject
{\bf References}\\
\begin{enumerate}
\item[[1]]
Fleischner, H., The square of every two-connected graph is
     Hamiltonian, J. Combinatorial Theory 3 (1974), 29-34
\item[[2]]
Harary, F., A. Schwenk, Trees with Hamiltonian squares,
     Mathematika, London 18 (1971), 138-140
\item[[3]]
Neuman, F., On a certain ordering of the vertices of a
     tree, \u{C}as. P\u{e}st. Mat. 89 (1964), 323-339
\item[[4]]
Schaar, G., Remarks on Hamiltonian properties of powers of
     digraphs, Discrete Applied Math. 51 (1994), 181-186
\item[[5]]
Schaar, G., On the Hamiltonicity exponent of directed cacti,
     submitted to Discrete Math.
\item[[6]]
Sekanina, M., On an ordering of the set of vertices of a
     connected graph, Publ.Fac.Univ. Brno 142 (1960), 137-140
\item[[7]]
Wojda, A.P., G. Schaar, An upper bound for the Hamiltonicity
     exponent of finite digraphs, submitted to Discrete Math.
\end{enumerate}

\address{TU Bergakademie Freiberg\\
	 Fakult\"at f. Mathematik und Physik\\
	 Bernhard-von-Cotta-Stra\ss e 2\\
	 D-09596 Freiberg\\
	 Germany}
\makeaddress
\end{document}

