CUBICAL HOMOLOGY OF ASYNCHRONOUS
TRANSITION SYSTEMS

A. A. Khusainov

###### Abstract

We show that a set with an action of a locally finite-dimensional free
partially commutative monoid and the corresponding semicubical set have
isomorpic homology groups. We build a complex of finite length for the
computing homology groups of any asynchronous transition system with finite
maximal number of mutually independent events. We give examples of computing
the homology groups.

2000 Mathematics Subject Classification 18G10, 18G35, 55U10, 68Q10, 68Q85

Keywords: semicubical set, homology of small categories, free partially
commutative monoid, trace monoid, asynchronous transition system.

## Introduction

By [1], an asynchronous transition system $(S,s_{0},E,I,{\rm Tran\,})$
consists of arbitrary sets $E$ and $S$ with a distinguished element $s_{0}\in
S$, an irreflexive symmetric relation $I\subseteq E\times E$, and a subset
${\rm Tran\,}\subseteq S\times E\times S$ satisfying the following axioms.

  1. (i)

for every $e\in E$, there are $s\in S$ and $s^{\prime}\in S$ such those
$(s,e,s^{\prime})\in{\rm Tran\,}$;

  2. (ii)

if $(s,e,s^{\prime})\in{\rm Tran\,}$ and $(s,e,s^{\prime\prime})\in{\rm
Tran\,}$, then $s^{\prime}=s^{\prime\prime}$;

  3. (iii)

for any pair $(e_{1},e_{2})\in I$ and triples $(s,e_{1},s_{1})\in{\rm
Tran\,}$, $(s_{1},e_{2},u)\in{\rm Tran\,}$ there exists $s_{2}\in S$ such that
$(s,e_{2},s_{2})\in{\rm Tran\,}$ and $(s_{2},e_{1},u)\in{\rm Tran\,}$.

Elements $s\in S$ are called states, $e\in E$ events, $s_{0}$ is an initial
state and $I\subseteq E\times E$ independence relation. Triples
$(s,e,s^{\prime})\in{\rm Tran\,}$ are transitions.

Asynchronous transition systems are introduced by Mike Shields [2] and Marek
Bednarczyk [3] for a simulation of concurrent computational systems. The
application of the partially commuting in parallel programming belongs to
Antoni Mazurkievicz. In [4], it was proposed to consider an asynchronous
transition system as a pointed set with action of a free partially commutative
monoid. It allows to introduce [4] and find approach to studying homology
groups of asynchronous transition systems [5]. Erik Goubault [6] and Philippe
Gaucher [7] have defined homology groups for higher dimensional automata,
which are other models of parallel computational systems. The our main result
(Theorem 3.3) shows that in some finiteness conditions, the homology groups of
asynchronous transition systems and of corresponding semiregular higher
dimensional automata are isomorpic (see Corollary 3.5). In [5], it was built
an algorithm to computing the first integer homology group of any asynchronous
transition system. In [8, 1], by a resolution of Ludmila Polyakova [9], it was
built a complex for the computations of homology groups in the case of finite
asynchronous transition system. We will build a complex for the computing the
homology groups of an asynchronous transition system without infinite sets of
mutually independent events (Corollary 3.9). If the maximal number of mutually
independent events is finite, then this complex has a finite length.

##  1 Homology of categories and semicubical sets

Let ${\mathcal{A}}$ be a category. Denote by ${\mathcal{A}}^{op}$ the opposite
category. Given $a,b\in{\rm Ob\,}{\mathcal{A}}$, let ${\mathcal{A}}(a,b)$ be
the set of all morphisms $a\rightarrow b$. For a small category
${\mathscr{C}}$, denote by ${\mathcal{A}}^{{\mathscr{C}}}$ the category of
functors ${\mathscr{C}}\rightarrow{\mathcal{A}}$ and natural transformations.

Throughout this paper let ${\rm Set}$ be the category of sets and maps, ${\rm
Ab}$ the category of abelian groups and homomorphisms, ${\,\mathbb{Z}}$ the
set or additive group of integers, ${\,\mathbb{N}}$ the set of nonnegative
integers or free monoid $\\{1,a,a^{2},\cdots\\}$ generated by one element. For
any family of abelian groups $\\{A_{j}\\}_{j\in J}$, the direct sum is denoted
by $\bigoplus\limits_{j\in J}A_{j}$. Elements of direct summands is written as
pairs $(j,g)$ with $j\in J$ and $g\in A_{j}$. If $A_{j}=A$ for all $j\in J$,
then the direct sum is denoted by $A^{(J)}$.

###  1.1 Semicubical sets

Suppose that ${\,\mathbb{I}}=\\{0,1\\}$ is the set ordered by $0<1$. For
integer $n\geqslant 0$, let ${\,\mathbb{I}}^{n}$ be the Cartesian power of
${\,\mathbb{I}}$. Denote by $\Box_{+}$ the category of partially ordered sets
${\,\mathbb{I}}^{n}$ and maps, which can be decomposed into compositions of
the increasing maps
$\delta_{i}^{k,\varepsilon}:{\,\mathbb{I}}^{k-1}\rightarrow{\,\mathbb{I}}^{k}$,
$1\leqslant i\leqslant k$, $\varepsilon\in{\,\mathbb{I}}$ defined by
$\delta_{i}^{k,\varepsilon}(x_{1},\cdots,x_{k-1})=(x_{1},\cdots,x_{i-1},\varepsilon,x_{i},\cdots,x_{k-1}).$

A semicubical set [10] is any functor $X:\Box_{+}^{op}{\rightarrow}{\rm Set}$.
Morphisms are defined as natural transformations. Since every morphism
$f:{\,\mathbb{I}}^{m}\rightarrow{\,\mathbb{I}}^{n}$ of the category $\Box_{+}$
has the canonical decomposition
$f=\delta_{j_{n-m}}^{n,\varepsilon_{n-m}}\cdots\delta_{j_{1}}^{m+1,\varepsilon_{1}}$
such that $1\leqslant j_{1}<\cdots<j_{n-m}\leqslant n$, a functor $X$ is
defined by values $X_{n}=X({\,\mathbb{I}}^{n})$ on objects and
$\partial_{i}^{k,\varepsilon}=X(\delta_{i}^{k,\varepsilon})$ on morphisms.
Hence a semicubical set may be given as a pair
$(X_{n},\partial_{i}^{n,\varepsilon})$ consisting of a sequnce of sets
$(X_{n})_{n\in{\,\mathbb{N}}}$ and a family of maps
$\partial_{i}^{n,\varepsilon}:X_{n}\rightarrow X_{n-1}$ defined for
$1\leqslant i\leqslant n$, $\varepsilon\in\\{0,1\\}$, and satisfying the
condition

$\partial_{i}^{n-1,\alpha}\circ\partial_{j}^{n,\beta}=\partial_{j-1}^{n-1,\beta}\circ\partial_{i}^{n,\alpha}~{},\mbox{
for }\alpha,\beta\in\\{0,1\\},n\geqslant 2,\mbox{ and }1\leqslant i<j\leqslant
n.$

For example, any directed graph given by a pair of maps ${\rm dom},{\rm
cod}:X_{1}\rightarrow X_{0}$ assigning to every arrow its source and target,
we can considered as the semicubical set with $\partial_{1}^{1,0}={\rm dom}$,
$\partial_{1}^{1,1}={\rm cod}$, and $X_{n}=\emptyset$ for all $n\geqslant 2$.
For $n\geqslant 2$, the maps $\partial_{i}^{n,\varepsilon}$ are empty. By
[10], cubical sets [11] provide examples of semicubical sets. Similarly, we
can define semicubical objects $(X_{n},\partial_{i}^{n,\varepsilon})$ in an
arbitrary category ${\mathcal{A}}$.

###  1.2 Homology of small categories

Homology groups of small categories with coefficients in functors into the
category of Abelian groups will be considered in this subsection.

Homology of categories and derived functors of the colimit.

###### Definition 1.1

Let ${\mathscr{C}}$ be a small category and $F:{\mathscr{C}}\rightarrow{\rm
Ab}$ a functor. Denote by $C_{*}({\mathscr{C}},F)$ a chain complex of Abelian
groups

$C_{n}({{\mathscr{C}}},F)=\bigoplus_{c_{0}\rightarrow\cdots\rightarrow
c_{n}}F(c_{0}),\quad n\geqslant 0,$

with differentials
$d_{n}=\sum\limits_{i=0}^{n}(-1)^{i}d^{n}_{i}:C_{n}({\mathscr{C}},F)\rightarrow
C_{n-1}({\mathscr{C}},F)$ defined for $n>0$ by the face operators

$d^{n}_{i}(c_{0}\stackrel{{\scriptstyle\alpha_{1}}}{{\rightarrow}}c_{1}\stackrel{{\scriptstyle\alpha_{2}}}{{\rightarrow}}\cdots\stackrel{{\scriptstyle\alpha_{n}}}{{\rightarrow}}c_{n},a)=\\\
\left\\{\begin{array}[]{ll}(c_{1}\stackrel{{\scriptstyle\alpha_{2}}}{{\rightarrow}}\cdots\stackrel{{\scriptstyle\alpha_{n}}}{{\rightarrow}}c_{n},F(c_{0}\stackrel{{\scriptstyle\alpha_{1}}}{{\rightarrow}}c_{1})(a))~{}~{},&\mbox{if}~{}i=0\\\
(c_{0}\stackrel{{\scriptstyle\alpha_{1}}}{{\rightarrow}}\cdots\stackrel{{\scriptstyle\alpha_{i-1}}}{{\rightarrow}}c_{i-1}\stackrel{{\scriptstyle\alpha_{i+1}\alpha_{i}}}{{\rightarrow}}c_{i+1}\stackrel{{\scriptstyle\alpha_{i+2}}}{{\rightarrow}}\cdots\stackrel{{\scriptstyle\alpha_{n}}}{{\rightarrow}}c_{n},a)\quad,&\mbox{if}~{}1\leqslant
i\leqslant n-1\\\
(c_{0}\stackrel{{\scriptstyle\alpha_{1}}}{{\rightarrow}}\cdots\stackrel{{\scriptstyle\alpha_{n-1}}}{{\rightarrow}}c_{n-1},a)~{}~{},&\mbox{if}~{}i=n\end{array}\right.$

The quotient groups $H_{n}(C_{*}({\mathscr{C}},F))={\rm Ker\,}(d_{n})/{\rm
Im\,}(d_{n+1})$ are called the $n$-th homology groups of the category
${\mathscr{C}}$ with coefficients in $F$.

It is known [10] that the functors $H_{n}(C_{*}({\mathscr{C}},-)):{\rm
Ab}^{\mathscr{C}}\rightarrow{\rm Ab}$ are natural isomorphic to left derived
of the colimit functor $\underrightarrow{\lim}^{\mathscr{C}}:{\rm
Ab}^{\mathscr{C}}\rightarrow{\rm Ab}$. So we will be denote them by
$\underrightarrow{\lim}_{n}^{\mathscr{C}}$.

For any small category ${\mathscr{C}}$, denote by
$\Delta_{\mathscr{C}}{\,\mathbb{Z}}$, or $\Delta{\,\mathbb{Z}}$ shortly, the
functor ${\mathscr{C}}\rightarrow{\rm Ab}$ with constant values
${\,\mathbb{Z}}$ on objects and $1_{\,\mathbb{Z}}$ on morphisms. The values of
left satellites
$\underrightarrow{\lim}_{n}^{\mathscr{C}}\Delta_{\mathscr{C}}{\,\mathbb{Z}}$
of the colimit functor on $\Delta_{\mathscr{C}}{\,\mathbb{Z}}$ are called the
homology groups of the category ${\mathscr{C}}$ and denoted by
$H_{n}({\mathscr{C}})$. It follows from Eilenberg’s Theorem [12, Appl. 2] that
homology groups of the geometric realization of the nerve of ${\mathscr{C}}$
are isomorphic to $H_{n}({\mathscr{C}})$. For example, if the category denoted
by ${\,\rm pt}$ consists of unique object and the identity morphism, then
$H_{n}({\,\rm pt})=0$ for all $n>0$ and $H_{0}({\,\rm pt})={\,\mathbb{Z}}$.

Coinitial functors. Let ${\mathscr{C}}$ be a small category. If
$H_{n}({\mathscr{C}})=0$ for $n>0$ and
$H_{0}({\mathscr{C}})\cong{\,\mathbb{Z}}$, then ${\mathscr{C}}$ is called
acyclic. Let $S:{\mathscr{C}}\rightarrow{\mathscr{D}}$ be a functor into an
arbitrary category ${\mathscr{D}}$. For any $d\in{\rm Ob\,}({\mathscr{D}})$, a
fibre (or comma-category [13]), denoted by $S/d$, is the category whose
objects ${\rm Ob\,}(S/d)$ consists of pairs $(c,\alpha)$ with $c\in{\rm
Ob\,}({\mathscr{C}})$, and $\alpha\in{\mathscr{D}}(S(c),d)$. Morphisms in
$S/d$ are triples $(f,\alpha_{1},\alpha_{2})$ of morphisms
$f\in{\mathscr{C}}(c_{1},c_{2})$, $\alpha_{1}\in{\mathscr{D}}(S(c_{1}),d)$,
and $\alpha_{2}\in{\mathscr{D}}(S(c_{2}),d)$ satisfying $\alpha_{2}\circ
S(f)=\alpha_{1}$. A forgetful functor $Q_{d}:S/d\rightarrow{\mathscr{C}}$ of
the fibre is defined by $Q_{d}(c,\alpha)=c$ on objects and
$Q_{d}(f,\alpha_{1},\alpha_{2})=f$ on morphisms. If the functor $S$ is a full
inclusion ${\mathscr{C}}\subseteq{\mathscr{D}}$, then $S/d$ is denoted by
${\mathscr{C}}/d$.

###### Definition 1.2

If the category $S/d$ is acyclic for every object $d\in{\mathscr{D}}$, then
functor $S:{\mathscr{C}}\rightarrow{\mathscr{D}}$ is called strongly
coinitial.

By [14, Theorem 2.3], it can be proved, that a functor
$S:{\mathscr{C}}\rightarrow{\mathscr{D}}$ between small categories is strongly
coinitial if and if the canonical morphisms
$\underrightarrow{\lim}_{n}^{{\mathscr{C}}^{op}}(F\circ
S^{op})\rightarrow\underrightarrow{\lim}_{n}^{{\mathscr{D}}^{op}}F$ are
isomorhisms for all functors and $n\geqslant 0$ [15, Proposition 1.4].

###  1.3 Homology of semicubical sets

Let $X\in{\rm Set}^{\Box_{+}^{op}}$ be a semicubical set. The category of
singular cubes $h_{*}/X$ is the fibre of the Yoneda Embedding
$h_{*}:\Box_{+}\rightarrow{\rm Set}^{\Box_{+}^{op}}$ over $X$. Consider a
category $\Box_{+}/X$ whose objects are elements
$\sigma\in\coprod\limits_{n\in{\,\mathbb{N}}}X_{n}$. Morhisms from $\sigma\in
X_{m}$ to $\tau\in X_{n}$ are given by triples $(\alpha,\sigma,\tau)$,
$\alpha\in\Box_{+}({\,\mathbb{I}}^{m},{\,\mathbb{I}}^{n})$, satifying
$X(\alpha)(\tau)=\sigma$. The categories $h_{*}/X$ and $\Box_{+}/X$ are
isomorphic and we will identify their. A homological system on a semicubical
set $X$ is any functor $F:(\Box_{+}/X)^{op}\rightarrow{\rm Ab}$.

Homology groups with coefficients in a homological system. We turn to study
homology groups $\underrightarrow{\lim}_{n}^{(\Box_{+}/X)^{op}}F$ of the
category of singular cubes with coefficients in a homological system $F$ on
$X$. Consider abelian groups $C_{n}(X,F)=\bigoplus\limits_{\sigma\in
X_{n}}F(\sigma)$. Define boundary operators
$d_{i}^{n,\varepsilon}:C_{n}(X,F)\rightarrow C_{n-1}(X,F)$ as homomorphisms
such those the following diagrams commute for $1\leqslant i\leqslant n$ and
$\varepsilon\in{\,\mathbb{I}}=\\{0,1\\}$,

$\begin{CD}\bigoplus\limits_{\sigma\in
X_{n}}F(\sigma)@>{d_{i}^{n,\varepsilon}}>{}>\bigoplus\limits_{\sigma\in
X_{n-1}}F(\sigma)\\\
@A{in_{\sigma}}A{}A@A{in_{X(\delta^{n,\varepsilon}_{i})(\sigma)}}A{}A\\\
F(\sigma)@>{F(\delta_{i}^{n,\varepsilon},X(\delta^{n,\varepsilon}_{i})(\sigma),\sigma)}>{}>F(X(\delta^{n,\varepsilon}_{i})(\sigma))\end{CD}$

###### Definition 1.3

Let $F:(\Box_{+}/X)^{op}\rightarrow{\rm Ab}$ be a homological system on a
semicubical set $X$. Homology groups $H_{n}(X,F)$ with coefficients in $F$ are
$n$-th homology groups of the complex $C_{*}(X,F)$ consisting of the groups
$C_{n}(X,F)=\bigoplus\limits_{\sigma\in X_{n}}F(\sigma)$ and differentials
$d_{n}=\sum\limits_{i=1}^{n}(-1)^{i}(d^{n,1}_{i}-d^{n,0}_{i})$.

Groups $H_{n}(X,\Delta{\,\mathbb{Z}})$ are called $n$-th integer homology
groups.

By [10, 4.3], for any semicubical set $X$ and a homological system $F$ on $X$,
there is isomorphisms $\underrightarrow{\lim}_{n}^{(\Box_{+}/X)^{op}}F\cong
H_{n}(X,F)$ for all $n\geqslant 0$. It follows that homology groups of cubical
sets studied in [11] and [16] are isomorphic to homology groups of the
corresponding semicubical sets with constant homological systems.

##  2 Homology of free partially commutative
monoids

In this section, we study a factorization category and semicubical set
concerned with a free partially commutative monoid. We will prove that
homology groups of the free partially commutative monoid and the corresponding
semicubical set are isomorphic. It allows us to build a complex to the
computing the homology groups of a free partially commutative monoid.

Each monoid $M$ will be considered as a category with ${\rm Ob\,}M=\\{M\\}$
consisting of the unique object and ${\rm Mor\,}M=M$. It has an influence on
denotations and terminology. In particular, a right $M$–set $X$, with the
action $(x,\mu)\mapsto x\cdot\mu$ for $x\in X$ and $\mu\in M$ is considered
and denoted as the functor ${X}:{M}^{op}\rightarrow{\rm Set}$ defined by
${X}(\mu)(x)=x\cdot\mu$. Morphisms of right $M$-sets are natural
transformations.

###  2.1 Homology of a free finitely generated commutative monoid

Category of factorizations. Suppose that ${\mathscr{C}}$ is a small category.
If a morphism $f\in{\rm Mor\,}{\mathscr{C}}$ belongs to ${\mathscr{C}}(a,b)$,
then we write ${\rm dom}f=a$ and ${\rm cod}f=b$. A category of factorizations
${\mathfrak{F}}{\mathscr{C}}$ [17] has the set of objects ${\rm
Ob\,}({\mathfrak{F}}{\mathscr{C}})={\rm Mor\,}({\mathscr{C}})$ and the sets of
morphisms ${\mathfrak{F}}{\mathscr{C}}(\alpha,\beta)$ consisting of all pairs
$(f,g)$ of $f\in{\mathscr{C}}({\rm dom}\beta,{\rm dom}\alpha)$ and
$g\in{\mathscr{C}}({\rm cod}\alpha,{\rm cod}\beta)$ satisfying
$g\circ\alpha\circ f=\beta$.

The composition of morphisms
$\alpha\stackrel{{\scriptstyle(f_{1},g_{1})}}{{\rightarrow}}\beta$ and
$\beta\stackrel{{\scriptstyle(f_{2},g_{2})}}{{\rightarrow}}\gamma$ is defined
by $\alpha\stackrel{{\scriptstyle(f_{1}\circ f_{2},g_{2}\circ
g_{1})}}{{\longrightarrow}}\gamma$. The identity of an object
$a\stackrel{{\scriptstyle\alpha}}{{\rightarrow}}b$ of the category
${\mathfrak{F}}{\mathscr{C}}$ consists of the pair of identity morphisms
$\alpha\stackrel{{\scriptstyle(1_{a},1_{b})}}{{\longrightarrow}}\alpha$. We
will study the category of factorizations of a monoid considered as a category
with an unique object. Denote by
${\mathfrak{F}}{\mathscr{C}}\stackrel{{\scriptstyle{\rm
cod}}}{{\rightarrow}}{\mathscr{C}}$ the functor that assigns to each
$a\rightarrow b$ its the codomain $b$ and to each morphism
$\alpha\stackrel{{\scriptstyle(f,g)}}{{\rightarrow}}\beta$ the morphism
$g:{\rm cod}(\alpha)\rightarrow{\rm cod}(\beta)$. By [15, Lemma 1.9], this
functor is strongly coinitial.

###### Lemma 2.1

Let ${\,\mathbb{N}}=\\{1,a,a^{2},\ldots\\}$ be the free monoid generated by
$a$ and let $T=\\{1,a\\}$. Suppose that
${\mathfrak{F}}{T}\subset{\mathfrak{F}}{\,\mathbb{N}}$ is full subcategory
with the set of objects $T$. Then the inclusion
${\mathfrak{F}}{T}\subset{\mathfrak{F}}{\,\mathbb{N}}$ is strongly coinitial.

Proof. The category ${\mathfrak{F}}{T}$ consists of two objects and two
morphisms $1\stackrel{{\scriptstyle(1,a)}}{{\rightarrow}}a$,
$1\stackrel{{\scriptstyle(a,1)}}{{\rightarrow}}a$ except the identity
morphisms. It easy to see that for any integer $p\geqslant 0$, the comma-
category ${\mathfrak{F}}{T}/a^{p}$ is the poset

$(1,1,a^{p})<(1,a,a^{p-1})>(a^{1},1,a^{p-1})<\cdots\\\
\cdots>(a^{s},1,a^{t})<(a^{s},a,a^{t-1})>(a^{s+1},1,a^{t-1})<\cdots>(a^{p},1,1)$

Since the geometric realization of its nerve is homeomorphic to the unit
segment, $H_{q}({\mathfrak{F}}{T}/a^{p})\cong H_{q}(pt)$ for all $q\geqslant
0$. ${\Box}$

Suppose that ${\,\mathbb{N}}$ is the free monoid generated by $a$. For
$n\geqslant 1$, denote $a_{1}=(a,1,\cdots,1)$, $a_{2}=(1,a,1,\cdots,1)$,
$\cdots$, $a_{n}=(1,\cdots,1,a)$. Consider the subset
$T^{n}\subset{\,\mathbb{N}}^{n}$ consisting of finite products
$a_{i_{1}}a_{i_{2}}\cdots a_{i_{k}}$ where $1\leqslant
i_{1}<i_{2}<\cdots<i_{k}\leqslant n$. Let ${\mathfrak{F}}T^{n}$ be the full
subcategory of ${\mathfrak{F}}{\,\mathbb{N}}^{n}$ with the class of objects
$T^{n}$. For every $\alpha=(a^{p_{1}},a^{p_{2}},\cdots,a^{p_{n}})$, the comma-
category ${\mathfrak{F}}T^{n}/\alpha$ is isomorphic to
$({\mathfrak{F}}T/a^{p_{1}})\times\cdots\times({\mathfrak{F}}T/a^{p_{n}})$. It
follows from the Künneth formula [15, Lemma 1.16] and Lemma 2.1 the following.

###### Lemma 2.2

The inclusion ${\mathfrak{F}}T^{n}\subset{\mathfrak{F}}{\,\mathbb{N}}^{n}$ is
strongly coinitial.

A semicubical set of a free finitely generated commutative monoid. Let
$a_{1}$, $a_{2}$, $\dots$, $a_{n}$ the above generators of
${\,\mathbb{N}}^{n}$. Consider the semicubical set $T^{n}_{*}$ consisting of
the subsets

$T^{n}_{k}=\\{a_{i_{1}}a_{i_{2}}\cdots a_{i_{k}}:1\leqslant
i_{1}<i_{2}<\cdots<i_{k}\leqslant n\\}$

and maps
$T^{n}_{k-1}~{}~{}{{{\partial^{k,0}_{s}}\atop\longleftarrow}\atop{\longleftarrow\atop{\partial^{k,1}_{s}}}}~{}~{}T^{n}_{k}~{}$,
$1\leqslant s\leqslant k$ defined as follows.

$\partial_{s}^{k,0}(a_{i_{1}}\cdots
a_{i_{k}})=\partial_{s}^{k,1}(a_{i_{1}}\cdots a_{i_{k}})=a_{i_{1}}\cdots
a_{i_{s-1}}\widehat{a_{i_{s}}}a_{i_{s+1}}\cdots a_{i_{k}}$

Here $a_{i_{1}}\cdots a_{i_{s-1}}\widehat{a_{i_{s}}}a_{i_{s+1}}\cdots
a_{i_{k}}$ is the word obtained by removing the symbol $a_{i_{s}}$. Objects of
the category $\Box_{+}/T^{n}_{*}$ may be considered as pairs $(k,\sigma)$
where $\sigma\in T^{n}_{k}$. Every $\sigma\in T^{n}_{k}$ has an unique
decomposition $a_{i_{1}}\cdots a_{i_{k}}$ such that $1\leqslant
i_{1}<\cdots<i_{k}\leqslant n$. And so the objects $(k,\sigma)$ may be
identify with elements $a_{i_{1}}\cdots a_{i_{k}}\in T^{n}$. Morphisms in
$\Box_{+}/T^{n}_{*}$ are triples

$(\delta:{\,\mathbb{I}}^{m}\rightarrow{\,\mathbb{I}}^{k},a_{j_{1}}\cdots
a_{j_{m}},a_{i_{1}}\cdots a_{i_{k}}),$

such those $T^{n}(\delta)(a_{j_{1}}\cdots a_{j_{m}})=a_{i_{1}}\cdots
a_{i_{k}}$.

We will establish a functor
${\mathfrak{S}}:\Box_{+}/T^{n}_{*}\rightarrow{\mathfrak{F}}T^{n}$. Toward this
end, define ${\mathfrak{S}}(a_{i_{1}}\cdots a_{i_{k}})=a_{i_{1}}\cdots
a_{i_{k}}$ on objects. Every morphism of the category $\Box_{+}/T^{n}_{*}$ has
a decomposition
$(\delta_{s}^{k,\varepsilon},a_{i_{1}}\cdots\widehat{a_{i_{s}}}\cdots
a_{i_{k}},a_{i_{1}}\cdots a_{i_{k}})$, $\varepsilon\in\\{0,1\\}$. Hence, it is
enough to define the values

${\mathfrak{S}}(\delta_{s}^{k,0},a_{i_{1}}\cdots\widehat{a_{i_{s}}}\cdots
a_{i_{k}},a_{i_{1}}\cdots
a_{i_{k}})=(a_{i_{s}},1):a_{i_{1}}\cdots\widehat{a_{i_{s}}}\cdots
a_{i_{k}}\rightarrow a_{i_{1}}\cdots a_{i_{k}}\\\
{\mathfrak{S}}(\delta_{s}^{k,1},a_{i_{1}}\cdots\widehat{a_{i_{s}}}\cdots
a_{i_{k}},a_{i_{1}}\cdots
a_{i_{k}})=(1,a_{i_{s}}):a_{i_{1}}\cdots\widehat{a_{i_{s}}}\cdots
a_{i_{k}}\rightarrow a_{i_{1}}\cdots a_{i_{k}}$ (1)

It is easy to see that the map ${\mathfrak{S}}$ has the unique functorial
extension.

For each $\sigma=a_{i_{1}}\cdots a_{i_{k}}$, the category
${\mathfrak{S}}/\sigma$ has the terminal object. Therefore, the following
assertion holds.

###### Lemma 2.3

The functor ${\mathfrak{S}}:\Box_{+}/T^{n}_{*}\rightarrow{\mathfrak{F}}T^{n}$
is strongly coinitial.

###  2.2 Homology of a free partially commutative monoid with coefficient in a
right module

###### Definition 2.1

Let $E$ be a set. Suppose that $I\subseteq E\times E$ is an irreflexive
symmetric relation on $E$. Monoid given by the set of generators $E$ and the
relations $ab=ba$ for all $(a,b)\in I$ is called free partially commutative
and denoted by $M(E,I)$. If $(a,b)\in I$, then the elements $a,b\in E$ are
called the commuting generators.

Our definition is more general than it is given in [18]. We do not demand that
the set $E$ is finite.

For any graph, a subgraph is called a $n$-clique if that is isomorphic to the
complete graph $K_{n}$. A clique is a subgraph which is equal to a $n$-clique
for some cardinal number $n\geqslant 1$. Let $M(E,I)$ be a free partially
commutative monoid given by a set of generators $E$ and relations $ab=ba$ for
all $(a,b)\in I$. Denote by $V$ the set of all maximal cliques of its
indepedence graph. For every $v\in V$, denote by $E_{v}\subseteq E$ the set of
vertices of $v$. The set $E_{v}$ is a maximal subset of $E$ consisting of
mutually commuting elements. The set $E_{v}$ generate the maximal commutative
submonoid $M(E_{v})\subseteq M(E,I)$. The monoid $M(E,I)$ is called locally
finite-dimensional if the sets $E_{v}$ are finite for all $v\in V$. This
property holds if and only if the independence graph does not contain infinite
cliques.

The coinitial subcategory of a category of factorizations. As above, V is the
set of maximal cliques in the independence graph of $M(E,I)$.

###### Proposition 2.4

Suppose for $v\in V$ that $T_{v}\subset M(E_{v})$ is the subset of products
$a_{1}a_{2}\cdots a_{n}$ of distinct elements $a_{j}\in E_{v}$, $1\leqslant
j\leqslant n$. Here $n$ may be taken finite values $\leqslant|E_{v}|$. It is
supposed that the product equals $1\in T_{v}$ for $n=0$. If $M(E,I)$ is
locally finite-dimensional, then the inclusion $\bigcup\limits_{v\in
V}{\mathfrak{F}}T_{v}\subset{\mathfrak{F}}M(E,I)$ is strongly coinitial.

Proof. The composition of strongly coinitial functors is strongly coinitial.
Since the inclusion $\bigcup\limits_{v\in
V}{\mathfrak{F}}M(E_{v})\subseteq{\mathfrak{F}}M(E,I)$ is strongly coinitial
by [15, Theorem 2.3], it is enough to show that the inclusion
$\bigcup\limits_{v\in V}{\mathfrak{F}}T_{v}\subset\bigcup\limits_{v\in
V}{\mathfrak{F}}M(E_{v})$ is strongly coinitial. For each
$\alpha\in\bigcup\limits_{v\in V}{\mathfrak{F}}M(E_{v})$, there is $w\in V$
such that $\alpha\in{\mathfrak{F}}M(E_{w})$. All divisors of $\alpha$ belong
to $M(E_{w})$. Hence $\bigcup\limits_{v\in
V}{\mathfrak{F}}T_{v}/\alpha={\mathfrak{F}}T_{w}/\alpha$. By Lemma 2.2, the
inclusion ${\mathfrak{F}}T_{w}\subset{\mathfrak{F}}M(E_{w})$ is strongly
coinitial. Therefore $H_{q}(\bigcup\limits_{v\in
V}{\mathfrak{F}}T_{v}/\alpha)\cong H_{q}(pt)$. ${\Box}$

Cubical homology of free partially commutative monoids. For an arbitrary set
$E$ with an irreflexive symmetric relation $I\subseteq E\times E$, we
construct a semicubical set $T(E,I)$ depending on a some total ordering
relationship $\leqslant$ on $E$. Toward this end for any integer $n>0$, we
define $T_{n}(E,I)$ as the set of all tuples $(a_{1},\cdots,a_{n})$ of
mutually commuting elements $a_{1}<\cdots<a_{n}$ in $E$,

$T_{n}(E,I)=\\{(a_{1},\cdots,a_{n}):(a_{1}<\cdots<a_{n})\&(1\leqslant
i<j\leqslant n\Rightarrow(a_{i},a_{j})\in I)\\}.$

The set $T_{0}(E,I)$ consists of unique empty word $1$. Maps
$\partial^{n,\varepsilon}_{i}:T_{n}(E,I)\rightarrow T(E,I)_{n-1}$ for
$1\leqslant i\leqslant n$ act as

$\partial^{n,0}_{i}(a_{1},\cdots,a_{n})=\partial^{n,1}_{i}(a_{1},\cdots,a_{n})=(a_{1},\cdots,\widehat{a_{i}},\cdots,a_{n})$
(2)

It easy to see that $T(E,I)$ is equal to union of the semicubical sets
$(T_{v})_{*}$ defined by

$(T_{v})_{n}=\\{(a_{1},\cdots,a_{n})\in T_{n}(E,I)~{}:~{}(1\leqslant
i\leqslant n\Rightarrow a_{i}\in E_{v})\\},$

where $E_{v}\subseteq E$ are the maximal subsets of mutually commuting
generators of $M(E,I)$. Face operators
$(T_{v})_{n}\stackrel{{\scriptstyle\partial^{n,\varepsilon}_{i}}}{{\rightarrow}}(T_{v})_{n-1}$
act for $1\leqslant i\leqslant n$ and $\varepsilon\in\\{0,1\\}$ by (2).

Let ${\mathfrak{S}}:\Box_{+}/\bigcup\limits_{v\in
V}(T_{v})_{*}\rightarrow\bigcup\limits_{v\in V}{\mathfrak{F}}T_{v}$ be the
functor assigning to every singular qube
$(a_{1},\cdots,a_{n})\in\bigcup\limits_{v\in V}(T_{v})_{n}$ the object
$a_{1}\cdots a_{n}$. The functor ${\mathfrak{S}}$ acts on morphisms by the
equation (1).

For each functor $F:M(E,I)^{op}\rightarrow{\rm Ab}$, denote by $\overline{F}$
a homological system on $T(E,I)$ defined as the composition

$(\Box_{+}/T(E,I))^{op}\stackrel{{\scriptstyle{\mathfrak{S}}^{op}}}{{\longrightarrow}}{\bigcup\limits_{v\in
V}({\mathfrak{F}}T_{v})^{op}}\subset({\mathfrak{F}}M(E,I))^{op}\stackrel{{\scriptstyle{\rm
cod}^{op}}}{{\longrightarrow}}M(E,I)^{op}\stackrel{{\scriptstyle
F}}{{\rightarrow}}{\rm Ab}$

We will suppose below that $E$ is a totally ordered set.

###### Proposition 2.5

Let $M(E,I)$ be a locally finite-dimensional free partially commutative monoid
and $F:M(E,I)^{op}\rightarrow{\rm Ab}$ a functor. The homology groups of
$M(E,I)$ are isomorphic to the cubical homology groups

$\underrightarrow{\lim}_{n}^{M(E,I)^{op}}F\cong
H_{n}(T(E,I),\overline{F}),\quad n\geqslant 0.$

Proof. The image of ${\mathfrak{S}}|_{\Box_{+}/(T_{v})_{*}}$ is contained in
the category ${\mathfrak{F}}T_{v}$ and defines a functor which we denote by
${\mathfrak{S}}_{v}:\Box_{+}/(T_{v})_{*}\rightarrow{\mathfrak{F}}T_{v}$. For
any $\alpha\in\bigcup\limits_{v\in V}{\mathfrak{F}}T_{v}$, there exists $w\in
V$ such that $\alpha\in{\mathfrak{F}}T_{w}$. It follows that there is an
isomorphism ${\mathfrak{S}}/\alpha\cong{\mathfrak{S}}_{w}/\alpha$. By Lemma
2.3, for every free finitely generated monoid $M(E_{v})$, the functor
${\mathfrak{S}}_{v}:\Box_{+}/(T_{v})_{*}\rightarrow{\mathfrak{F}}T_{v}$ is
strongly coinitial. Consequently, the category ${\mathfrak{S}}_{v}/\alpha$ is
acyclic. It follows that ${\mathfrak{S}}/\alpha$ is acyclic. Thus
${\mathfrak{S}}$ is strongly coinitial. Using the strong coinitiality of the
inclusion $\bigcup\limits_{v\in
V}{\mathfrak{F}}T_{v}\subseteq{\mathfrak{F}}M(E,I)$, we have the isomorphisms

$\underrightarrow{\lim}_{n}^{M(E,I)^{op}}F\cong\underrightarrow{\lim}_{n}^{(\Box_{+}/\bigcup\limits_{v\in
V}(T_{v})_{*})^{op}}~{}\overline{F}$

${\Box}$

It allows us to construct the following complex for the computing the groups
$\underrightarrow{\lim}_{n}^{M(E,I)^{op}}F$.

###### Corollary 2.6

Suppose that $M(E,I)$ is a locally finite-dimensional free partially
commutative monoid. Then for any right $M(E,I)$-module $G$, the groups
$H_{n}(M(E,I)^{op},G)$ are isomorphic to homology groups of the complex

$0\leftarrow G\stackrel{{\scriptstyle
d_{1}}}{{\leftarrow}}\bigoplus\limits_{a_{1}\in
T_{1}(E,I)}G\stackrel{{\scriptstyle
d_{2}}}{{\leftarrow}}\bigoplus\limits_{(a_{1},\ldots,a_{n})\in
T_{n}(E,I)}G\leftarrow\cdots\\\
\cdots\leftarrow\bigoplus\limits_{(a_{1},\ldots,a_{n-1})\in
T_{n-1}(E,I)}G\stackrel{{\scriptstyle
d_{n}}}{{\longleftarrow}}\bigoplus\limits_{(a_{1},\ldots,a_{n})\in
T_{n}(E,I)}G\leftarrow\cdots~{},$

the $n$-th member of that for each $n\geqslant 0$ equals a direct sum of
backup copies of the abelian group $G$ in all $n$-tuples of mutually commuting
elements $a_{1}<a_{2}<\cdots<a_{n}$ in $E$ where the differentials are defined
by

$d_{n}(a_{1},\cdots,a_{n},g)=\sum\limits_{s=1}^{n}(-1)^{s}(a_{1},\cdots,\widehat{a_{s}},\cdots,a_{n},G(a_{s})(g)-g)$
(3)

##  3 Homology of sets with an action of a free partially commutative monoid

This section is devoted to homology groups of right $M(E,I)$-sets $X$ with
coefficients in functors $F:(M(E,I)/X)^{op}\rightarrow{\rm Ab}$. We show that
these groups may be studied as the homology groups of the monoid $M(E,I)$. We
prove the main result of this paper about the isomorphism of homology groups
of any $M(E,I)$-set $X$ and the corresponding semicubical set $Q_{*}X$. This
result is applied for the computing homology groups of state spaces in the
simplest cases.

###  3.1 Homology of right $M(E,I)$-sets

Let $M$ be a monoid and $X\in{\rm Set}^{M^{op}}$ a right $M$-set. Suppose that
$F:(M/X)^{op}\rightarrow{\rm Ab}$ is a functor. Consider a functor
$S=Q^{op}:(M/X)^{op}\rightarrow M^{op}$ opposite to the forgetful functor of
the fibre. Let ${\rm Lan}^{S}F:M^{op}\rightarrow Ab$ be the left Kan extension
[13] of the functor $F$ along to $S$. Objects of the category $(M/X)^{op}$ may
be considered as elements $x\in X$. Morphisms between them are triples
$x\stackrel{{\scriptstyle\mu}}{{\rightarrow}}y$ such those $\mu\in M$ and
$x\cdot\mu=y$. We get the following assertion by replacing a monoid instead of
the category in [10, Proposition 3.7].

###### Lemma 3.1

A right $M$-module ${\rm Lan}^{S}F$ is the Abelian group
$\bigoplus\limits_{x\in X}F(x)$ with the action on $(x,f)$ with $x\in X$ and
$f\in F(x)$ defined by

$(x,f)\mu={\rm
Lan}^{S}F(\mu)(x,f)=(x\cdot\mu,F(x\stackrel{{\scriptstyle\mu}}{{\rightarrow}}x\cdot\mu)(f)).$

There are isomorphisms
$\underrightarrow{\lim}_{n}^{(M/X)^{op}}F\cong\underrightarrow{\lim}_{n}^{M^{op}}{\rm
Lan}^{S}{F}$ for all $n\geqslant 0$.

Let $X$ be a right $M(E,I)$-set. Consider an arbitrary total ordering on $E$.
Define sets

$Q_{n}X=\\{(x,a_{1},\cdots,a_{n}):a_{1}<\cdots<a_{n}\&(1\leqslant i<j\leqslant
n\Rightarrow(a_{i},a_{j})\in I)\\}.$

In particular $Q_{0}X=X$. Define the maps

$Q_{n}X{{{\partial^{n,0}_{i}}\atop{\longrightarrow}}\atop{{\longrightarrow}\atop{\partial^{n,1}_{i}}}}Q_{n-1}X~{},\quad
n\geqslant 1~{},~{}~{}1\leqslant i\leqslant n~{},$

by

${\partial^{n,\varepsilon}_{i}}(x,a_{1},\cdots,a_{n})=(x\cdot
a_{i}^{\varepsilon},a_{1},\cdots,\widehat{a_{i}},\cdots,a_{n})~{},\varepsilon\in\\{0,1\\},$

where $a_{i}^{0}=1$ $a_{i}^{1}=a_{i}$.

###### Lemma 3.2

The sequence of the sets $Q_{n}X$ and the family of maps
${\partial^{n,0}_{i}}$, ${\partial^{n,1}_{i}}$ make up a semicubical set.

For any functor $F:(M(E,I)/X)^{op}\rightarrow{\rm Ab}$, we build the
homological system $\overline{F}:(\Box_{+}/Q_{*}X)^{op}\rightarrow{\rm Ab}$ as
follows. Define $\overline{F}(x,a_{1},\cdots,a_{n})=F(x)$ on objects and
$\overline{F}(\delta_{i}^{n,\varepsilon},\partial_{i}^{n,\varepsilon}(\sigma),\sigma)=F(x\stackrel{{\scriptstyle
a_{i}^{\varepsilon}}}{{\rightarrow}}xa_{i}^{\varepsilon})$ on morphisms for
$\sigma=(x,a_{1},\cdots,a_{n})$.

###### Theorem 3.3

Let $M(E,I)$ be a locally finite-dimensional free partially commutative monoid
and $X$ a right $M(E,I)$-set. Suppose $F:(M(E,I)/X)^{op}\rightarrow{\rm Ab}$
is a functor and $\overline{F}:(\Box_{+}/Q_{*}X)^{op}\rightarrow{\rm Ab}$ the
corresponding homological system of Abelian groups. Then
$\underrightarrow{\lim}_{n}^{(M(E,I)/X)^{op}}F\cong
H_{n}(Q_{*}X,\overline{F})$ for all $n\geqslant 0$. In other words,
$\underrightarrow{\lim}_{n}^{(M(E,I)/X)^{op}}F$ are isomorphic to homology
groups of the complex

$0\leftarrow\bigoplus\limits_{x\in Q_{0}X}F(x)\stackrel{{\scriptstyle
d_{1}}}{{\leftarrow}}\bigoplus\limits_{(x,a_{1})\in
Q_{1}X}F(x)\stackrel{{\scriptstyle
d_{2}}}{{\leftarrow}}\bigoplus\limits_{{(x,a_{1},a_{2})\in
Q_{2}X}}F(x)\leftarrow\cdots\\\
\cdots\leftarrow\bigoplus\limits_{(x,a_{1},\cdots,a_{n-1})\in
Q_{n-1}X}F(x)\stackrel{{\scriptstyle
d_{n}}}{{\longleftarrow}}\bigoplus\limits_{{(x,a_{1},\cdots,a_{n})\in
Q_{n}X}}F(x)\leftarrow\cdots~{},$

where $d_{n}(x,a_{1},\cdots,a_{n},f)=$

$\sum_{s=1}^{n}(-1)^{s}((x\cdot
a_{s},a_{1},\cdots,\widehat{a_{s}},\cdots,a_{n},F(x\stackrel{{\scriptstyle
a_{s}}}{{\rightarrow}}x\cdot a_{s})(f))\\\
-(x,a_{1},\cdots,\widehat{a_{s}},\cdots,a_{n},f))$

Proof. Applying Lemma 3.1 to the monoid $M=M(E,I)$ gives the following complex
for a computation of homology groups with coefficients in ${\rm Lan}^{S}F$ by
Corollary 2.6.

$0\leftarrow{\rm Lan}^{S}F\stackrel{{\scriptstyle
d_{1}}}{{\leftarrow}}\bigoplus\limits_{a_{1}\in T_{1}(E,I)}{\rm
Lan}^{S}F\stackrel{{\scriptstyle
d_{2}}}{{\leftarrow}}\bigoplus\limits_{(a_{1},a_{2})\in T_{2}(E,I)}{\rm
Lan}^{S}F\leftarrow\cdots\\\
\cdots\leftarrow\bigoplus\limits_{(a_{1},a_{2},\cdots,a_{n-1})\in
T_{n-1}(E,I)}{\rm Lan}^{S}F\stackrel{{\scriptstyle
d_{n}}}{{\longleftarrow}}\bigoplus\limits_{(a_{1},a_{2},\cdots,a_{n})\in
T_{n}(E,I)}{\rm Lan}^{S}F\leftarrow\cdots$

where the differentials are defined by (3). For $(a_{1},\ldots,a_{n})\in
T_{n}(E,I)$ and $g\in{\rm Lan}^{S}F$, the values $d_{n}(a_{1},\cdots,a_{n},g)$
are equal to

$\sum\limits_{s=1}^{n}(-1)^{s}(a_{1},\cdots,\widehat{a_{s}},\cdots,a_{n},{\rm
Lan}^{S}F(a_{s})(g))-\sum\limits_{s=1}^{n}(-1)^{s}(a_{1},\cdots,\widehat{a_{s}},\cdots,a_{n},g)$

Substituting $g=(x,f)\in\bigoplus\limits_{x\in X}F(x)={\rm Lan}^{S}F$ and
taking into account the equality ${\rm Lan}^{S}F(a_{s})(x,f)=(x\cdot
a_{s},F(x\stackrel{{\scriptstyle a_{s}}}{{\rightarrow}}x\cdot a_{s})(f))$
realized by Lemma 3.1, we obtain

$d_{n}(x,a_{1},\cdots,a_{n},f)=\sum_{s=1}^{n}(-1)^{s}(x\cdot
a_{s},a_{1},\cdots,\widehat{a_{s}},\cdots,a_{n},F(x\stackrel{{\scriptstyle
a_{s}}}{{\rightarrow}}x\cdot a_{s})(f))\\\
-\sum_{s=1}^{n}(-1)^{s}(x,a_{1},\cdots,\widehat{a_{s}},\cdots,a_{n},f)$

${\Box}$

###### Corollary 3.4

Suppose that $M(E,I)$ is locally finite-dimensional. Then for any right
$M(E,I)$-set $X$, the groups
$\underrightarrow{\lim}_{n}^{(M(E,I)/X)^{op}}\Delta{\,\mathbb{Z}}$ are
isomorphic to integer homology groups of the semicubical set $Q_{*}X$.

###### Conjecture 1

If $M(E,I)$ is locally finite-dimensional, then for each right $M(E,I)$-set
$X$, the homology group
$\underrightarrow{\lim}_{1}^{(M(E,I)/X)^{op}}\Delta{\,\mathbb{Z}}$ is torsion-
free.

###### Example 3.1

Suppose that $P=\\{\star\\}$ is the right $M(E,I)$-set over a locally finite-
dimensional free partially commutative monoid $M(E,I)$. By Theorem 3.3, the
groups $\underrightarrow{\lim}_{n}^{(M(E,I)/P)^{op}}\Delta{\,\mathbb{Z}}$ are
isomorphic to the homology groups of the complex

$0\leftarrow{\,\mathbb{Z}}\stackrel{{\scriptstyle
d_{1}}}{{\longleftarrow}}\bigoplus\limits_{(\star,a_{1})\in
Q_{1}P}{\,\mathbb{Z}}\stackrel{{\scriptstyle
d_{2}}}{{\longleftarrow}}\bigoplus\limits_{(\star,a_{1},a_{2})\in
Q_{2}P}{\,\mathbb{Z}}\leftarrow\cdots\\\
\cdots~{}~{}~{}\leftarrow\bigoplus\limits_{(\star,a_{1},a_{2},\cdots,a_{n-1})\in
Q_{n-1}P}{\,\mathbb{Z}}\stackrel{{\scriptstyle
d_{n}}}{{\longleftarrow}}\bigoplus\limits_{(\star,a_{1},a_{2},\cdots,a_{n})\in
Q_{n}P}{\,\mathbb{Z}}\leftarrow\cdots~{},$

where $d_{n}(\star,a_{1},\cdots,a_{n})=0$. Consequently,
$\underrightarrow{\lim}_{n}^{(M(E,I)/P)^{op}}\Delta{\,\mathbb{Z}}\cong{\,\mathbb{Z}}^{(p_{n})}$
where $p_{n}$ is the cardinality of the set of the subsets
$\\{a_{1},\cdots,a_{n}\\}\subseteq E$ consisting of mutually commuting
elements. Here $p_{0}=1$ as the number of empty subsets.

###  3.2 Homology of asynchronous transition systems

Following [8], we will consider an asynchronous transition system as a
nondegenerated space of states with a distinguished initial point. Recall that
the category of sets and partially functions may be considered as the category
of pointed sets.

Partially functions and pointed maps. A pointed set $X$ is a set with a
distinguished element denoted by $\star$. A map $f:X\rightarrow Y$ between
pointed sets is pointed if it satisfy $f(\star)=\star$.

Let ${\rm Set}_{*}$ be the category of pointed sets and pointed maps between
them. Denote by $\sqcup$ the disjoint union. The category of sets and maps
${\rm Set}$ admits the inclusion into ${\rm Set}_{*}$ which assign to every
set $S$ the pointed set $S_{*}=S\sqcup\\{\star\\}$ and to each map
$\sigma:S\rightarrow S^{\prime}$ the map $\sigma_{*}:S_{*}\rightarrow
S^{\prime}_{*}$ defined by $\sigma_{*}(s)=\sigma(s)$ for $s\in S$ and
$\sigma_{*}(\star)=\star$.

For any partially function $f:X\rightharpoonup Y$ defined in a subset
$Domf\subseteq X$, we may define the corresponding pointed map
$f_{*}:X_{*}\rightarrow Y_{*}$ by

$f_{*}(x)=\left\\{\begin{array}[]{ll}f(x)&\mbox{if}\quad x\in Domf,\\\
{\star}&\mbox{otherwise}.\end{array}\right.$

By [3], this correspondence show that the category of sets and partially
functions is equivalent to ${\rm Set}_{*}$.

Category of state spaces.

###### Definition 3.2

A state space $\Sigma=(S,E,I,{\rm Tran\,})$ consists of sets $S$ and $E$, a
subset ${\rm Tran\,}\subseteq S\times E\times S$, and an irreflexive
antisymmetric relation $I\subseteq E\times E$ satisfying to the following two
axioms.

  1. (i)

if $(s,e,s^{\prime})\in{\rm Tran\,}$ and $(s,e,s^{\prime\prime})\in{\rm
Tran\,}$, then $s^{\prime}=s^{\prime\prime}$;

  2. (ii)

for any pair $(e_{1},e_{2})\in I$ and triples $(s,e_{1},s_{1})\in{\rm Tran\,}$
and $(s_{1},e_{2},v)\in{\rm Tran\,}$, there exists $s_{2}\in S$ such that
$(s,e_{2},s_{2})\in{\rm Tran\,}$ and $(s_{2},e_{1},v)\in{\rm Tran\,}$.

Elements $s\in S$ are called states, $(s,e,s^{\prime})\in{\rm Tran\,}$
transitions, $e\in E$ events. $I$ is the independence relation.

A state space is called nondegenerate if it satisfies the condition that for
every $e\in E$ there exist $s,s^{\prime}\in S$ such those
$(s,e,s^{\prime})\in{\rm Tran\,}$.

Let ${\mathcal{S}}$ denote the category of state spaces and morphisms

$(\sigma,\eta):(S,E,{\rm Tran\,},I)\rightarrow(S^{\prime},E^{\prime},{\rm
Tran\,}^{\prime},I^{\prime})$

given by maps $\sigma:S\rightarrow S^{\prime}$ and pointed maps
$\eta:E_{*}\rightarrow E^{\prime}_{*}$ satisfying the conditions

  1. (i)

for any $(s_{1},e,s_{2})\in{\rm Tran\,}$, if $\eta(e)\not=\star$, then
$(\sigma(s_{1}),\eta(e),\sigma(s_{2}))\in{\rm Tran\,}^{\prime}$, otherwise
$\sigma(s_{1})=\sigma(s_{2})$;

  2. (ii)

if $(e_{1},e_{2})\in I$, $\eta(e_{1})\not=\star$, $\eta(e_{2})\not=\star$,
then $(\eta(e_{1}),\eta(e_{2}))\in I^{\prime}$.

This definition with the condition $\sigma(s_{0})=s^{\prime}_{0}$ gives the
definition of morphisms between asynchronous transition systems. For $\eta$
satisfying the condition (ii), let $\eta_{\bullet}:E\rightarrow
E^{\prime}\cup\\{1\\}$ denote the map

$\eta_{\bullet}=\left\\{\begin{array}[]{ll}\eta(e),&\mbox{if}~{}\eta(e)~{}\mbox{is
defined},\\\ 1,&\mbox{otherwise}\end{array}\right.$

Let $\widetilde{\eta_{\bullet}}:M(E,I)\rightarrow M(E^{\prime},I^{\prime})$ be
the extension of $\eta_{\bullet}$ to the monoid homomorphism.

By [8, Proposition 2], every object $\Sigma$ of $\mathcal{S}$ may be given as
a pointed set $S_{*}=S\sqcup\\{\star\\}$ with a right action of a free
partially commutative monoid. There is a correspondence assigning to any
morphism from $\Sigma:M(E,I)^{op}\rightarrow{\rm Set}_{*}$ to
$\Sigma^{\prime}:M(E^{\prime},I^{\prime})^{op}\rightarrow{\rm Set}_{*}$ the
diagram

---
$\textstyle{M(E,I)^{\rm
op}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\widetilde{\eta_{\bullet}}^{\rm
op}}$$\scriptstyle{\Sigma}$$\textstyle{M(E^{\prime},I^{\prime})^{\rm
op}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{{\Sigma^{\prime}}}$$\textstyle{{\nearrow}_{\sigma_{*}}}$$\textstyle{{\rm
Set}_{*}}$

in which
$\sigma_{*}:\Sigma\rightarrow\Sigma^{\prime}\circ\widetilde{\eta_{\bullet}}^{op}$
is the natural transformation mapping $S$ into $S^{\prime}$ by $\sigma$. It
easy to see that the morphism is given by a pair $(\sigma,\varphi)$ consisting
of a map $\sigma:S\rightarrow S^{\prime}$ and a monoid homomorphism
$\varphi:M(E,I)\rightarrow M(E^{\prime},I^{\prime})$ such those
$\varphi(E)\subseteq E^{\prime}\cup\\{1\\}$
$\sigma_{*}(se)=\sigma_{*}(s)\varphi(e)$ for all $s\in S$ and $e\in E$.

Homology of state spaces. Let $U:{\rm Set}_{*}\rightarrow{\rm Set}$ be a
functor which simply forgets the distinguished points. For any state space
$\Sigma:M(E,I)^{op}\rightarrow{\rm Set}_{*}$ the composition $U\circ\Sigma$ is
a right $M(E,I)$-set. Denote by $K_{*}(\Sigma)$ the category
$(M(E,I)/(U\circ\Sigma))^{op}$. Its objects may be considered as elements in
$S_{*}$, and morphisms are triples
$s_{1}\stackrel{{\scriptstyle\mu}}{{\rightarrow}}s_{2}$, $\mu\in M(E,I)$,
$s_{1}\in S_{*}$, $s_{2}\in S_{*}$. Composition of morphisms
$(s_{2}\stackrel{{\scriptstyle\mu_{2}}}{{\rightarrow}}s_{3})\circ(s_{1}\stackrel{{\scriptstyle\mu_{1}}}{{\rightarrow}}s_{2})$
equals $(s_{1}\stackrel{{\scriptstyle\mu_{1}\mu_{2}}}{{\rightarrow}}s_{3})$.

Homology groups of a state space with coefficients in a functor
$F:K_{*}(\Sigma)\rightarrow{\rm Ab}$ are defined by
$H_{n}(\Sigma,F)=\underrightarrow{\lim}_{n}^{K_{*}(\Sigma)}F$ for $n\geqslant
0$.

Semi-regular higher-dimensional automata [6] are precisely the semicubical
sets. So for such automata $X$, there are defined homology groups $H_{n}(X,F)$
with coefficients in homological systems $F$. It follows from Theorem 3.3 the
following assertion.

###### Corollary 3.5

Let $\Sigma=(S,E,I,{\rm Tran\,})$ be a state space. If $M(E,I)$ is locally
finite-dimensional, then $H_{n}(\Sigma,F)\cong
H_{n}(Q_{*}(U\circ\Sigma),\overline{F})$ for all $n\geqslant 0$.

Direct summands of integer homology groups. We will show that the homology
groups of the one-point set considered in Example 3.1 are direct summands of
$H_{n}(\Sigma,\Delta{\,\mathbb{Z}})$. To that end we define functors with
values ${\,\mathbb{Z}}$ and $0$ on objects. For a small category
${\mathscr{C}}$, a subset $S\subseteq{\rm Ob\,}{\mathscr{C}}$ is called closed
in ${\mathscr{C}}$ if it contains with any $s\in S$ all objects $c\in{\rm
Ob\,}{\mathscr{C}}$ those admit morphisms $s\rightarrow c$. For example, the
subset $\\{\star\\}$ is closed in $K_{*}(\Sigma)$. The complement of a closed
subset in ${\rm Ob\,}{\mathscr{C}}$ is called open. If a set $S\subseteq{\rm
Ob\,}{\mathscr{C}}$ is equal to the intersection of an open subset and a
closed subset, then we can define a functor ${\,\mathbb{Z}}[S]$ by

${\,\mathbb{Z}}[S](c)=\left\\{\begin{array}[]{ll}{\,\mathbb{Z}}&\mbox{if}~{}~{}c\in
S,\\\ 0,&\mbox{otherwise,}\end{array}\right.$

on objects $c\in{\rm Ob\,}{\mathscr{C}}$. We put
${\,\mathbb{Z}}[S](c_{1}\rightarrow c_{2})=1_{{\,\mathbb{Z}}}$ if $c_{1}\in S$
and $c_{2}\in S$, and ${\,\mathbb{Z}}[S](c_{1}\rightarrow c_{2})=0$ on the
other morphisms.

###### Proposition 3.6

Suppose that $\Sigma=(S,E,I,{\rm Tran\,})$ is an arbitrary state space. Then
$H_{n}(\Sigma,\Delta{\,\mathbb{Z}})\cong{\,\mathbb{Z}}^{(p_{n})}\oplus
H_{n}(\Sigma,{\,\mathbb{Z}}[S])$ for all $n\geqslant 0$.

Proof. Consider the full subcategory $K_{*}(\emptyset)\subseteq K_{*}(\Sigma)$
with ${\rm Ob\,}(K_{*}(\emptyset))=\\{\star\\}$. The inclusion of this full
subcategory is a coretraction. The exact sequence
$0\rightarrow{\,\mathbb{Z}}[\star]\rightarrow\Delta{\,\mathbb{Z}}\rightarrow{\,\mathbb{Z}}[S]\rightarrow
0$ in ${\rm Ab}^{K_{*}(\Sigma)}$ gives the exact sequence of complexes

$0\rightarrow C_{*}(K_{*}(\Sigma),{\,\mathbb{Z}}[\star])\rightarrow
C_{*}(K_{*}(\Sigma),\Delta{\,\mathbb{Z}})\rightarrow
C_{*}(K_{*}(\Sigma),{\,\mathbb{Z}}[S])\rightarrow 0$ (4)

The chain homomorphism $C_{*}(K_{*}(\Sigma),{\,\mathbb{Z}}[\star])\rightarrow
C_{*}(K_{*}(\Sigma),\Delta{\,\mathbb{Z}})$ is equal to the composition of the
isomorphism $C_{*}(K_{*}(\Sigma),{\,\mathbb{Z}}[\star])\rightarrow
C_{*}(K_{*}({\emptyset}),\Delta{\,\mathbb{Z}})$ and coretraction
$C_{*}(K_{*}({\emptyset}),\Delta{\,\mathbb{Z}})\rightarrow
C_{*}(K_{*}(\Sigma),\Delta{\,\mathbb{Z}})$. Hence the exact sequence (4)
splits. The corresponding exact sequence of $n$-th homology groups gives the
required assertion. $\Box$

In particular, if $H_{n}(\Sigma,\Delta{\,\mathbb{Z}})\cong H_{n}({\,\rm pt})$
for all $n\geqslant 0$, then $p_{n}=0$ for $n>0$. In this case $E=\emptyset$,
$I=\emptyset$, and hence $K_{*}(\Sigma)$ is a discrete category. Since
$H_{0}(K_{*}(\Sigma))={\,\mathbb{Z}}$, this category has an unique object.
Consequently, $S=\emptyset$. It follows the following assertion important for
the calassification of state spaces.

###### Corollary 3.7

Let $\Sigma=(S,E,I,{\rm Tran\,})$ be a state space. If
$H_{n}(\Sigma,\Delta{\,\mathbb{Z}})=0$ for all $n>0$ and
$H_{0}(\Sigma,\Delta{\,\mathbb{Z}})={\,\mathbb{Z}}$, then $S=E=I={\rm
Tran\,}=\emptyset$.

Computing homology groups the state space consisting of an unique element. It
may be seemed that the homology groups of state spaces are torsion-free. We
will show that this opinion is wrong.

Recall that a simplicial scheme is a pair $(X,\mathfrak{M})$ consisting of a
set $X$ and a set $\mathfrak{M}$ of its finite nonempty subsets satisfying the
following conditions

  1. (i)

$x\in X\Rightarrow\\{x\\}\in\mathfrak{M}$

  2. (ii)

$S\subseteq T\in\mathfrak{M}\Rightarrow S\in\mathfrak{M}$.

Let $(X,\mathfrak{M})$ be a simplicial set. Consider an arbitrary total
ordering $<$ on $X$. Denote

$X_{n}=\\{(x_{0},x_{1},\cdots,x_{n}):\\{x_{0},x_{1},\cdots,x_{n}\\}\in\mathfrak{M}\quad\&\quad
x_{0}<x_{1}<\cdots<x_{n}\\}.$

For any set $S$, let $L(S)$ be a free Abelian group generated by $S$. Consider
a family of Abelian groups

$C_{n}(X,\mathfrak{M})=\left\\{\begin{array}[]{ll}L(X_{n})&$for$\quad
n\geqslant 0,\\\ 0,&$otherwise$.\end{array}\right.$

Define homomorphisms $d_{n}:C_{n}(X,\mathfrak{M})\rightarrow
C_{n-1}(X,\mathfrak{M})$ on the generators by

$d_{n}(x_{0},x_{1},\cdots,x_{n})=\sum_{i=0}^{n}(-1)^{i}(x_{0},\cdots,x_{i-1},x_{i+1},\cdots,x_{n}).$

It is well known that the family $(C_{n}(X,\mathfrak{M}),d_{n})$ is a chain
complex. Denote $C_{*}(X,\mathfrak{M})=(C_{n}(X,\mathfrak{M}),d_{n})$. We can
prove that homology groups of the complex $C_{*}(X,\mathfrak{M})$ does not
depend on the total ordering of $X$. They are called the homology groups
$H_{n}(X,\mathfrak{M})$ of the simplicial scheme $(X,\mathfrak{M})$.

###### Theorem 3.8

Let $\Sigma=(\\{x_{0}\\},E,I,{\rm Tran\,})$ be a state space. Suppose that the
action of $M(E,I)$ is defined by $x_{0}\cdot a=\star$ for every $a\in E$. Let
$(E,\mathfrak{M})$ be a simplicial scheme where $\mathfrak{M}$ consists of
nonempty finite subsets of mutually commuting generators and let
$p_{n}=|E_{n-1}|$ denote the cardinal number of $n$-cliques in the
independence graph of $M(E,I)$. If $M(E,I)$ is locally finite-dimensional,
then $H_{n}(\Sigma,\Delta{\,\mathbb{Z}})\cong{\,\mathbb{Z}}^{(p_{n})}\oplus
H_{n-1}(E,\mathfrak{M})$ for all $n\geqslant 2$.

Proof. Let ${\,\mathbb{Z}}[x_{0}]:K_{*}(\Sigma)\rightarrow{\rm Ab}$ be the
functor with values ${\,\mathbb{Z}}[x_{0}](x_{0})={\,\mathbb{Z}}$ and
${\,\mathbb{Z}}[x_{0}](\star)=0$. By Theorem 3.3, the homology groups
$H_{n}(\Sigma,{\,\mathbb{Z}}[x_{0}])=\underrightarrow{\lim}_{n}^{(M(E,I)/(U\circ\Sigma))^{op}}{\,\mathbb{Z}}[x_{0}]$
are isomorphic to the homology groups of the complex

$0\leftarrow{\,\mathbb{Z}}\stackrel{{\scriptstyle
d_{1}}}{{\longleftarrow}}\bigoplus\limits_{a_{1}\in
E_{1}}{\,\mathbb{Z}}\stackrel{{\scriptstyle
d_{2}}}{{\longleftarrow}}\bigoplus\limits_{(a_{1},a_{2})\in
E_{2}}{\,\mathbb{Z}}\leftarrow\cdots\\\
\cdots\leftarrow\bigoplus\limits_{(a_{1},a_{2},\cdots,a_{n-1})\in
E_{n-1}}{\,\mathbb{Z}}\stackrel{{\scriptstyle
d_{n}}}{{\longleftarrow}}\bigoplus\limits_{(a_{1},a_{2},\cdots,a_{n})\in
E_{n}}{\,\mathbb{Z}}\leftarrow\cdots~{},$

with the differentials
$d_{n}(a_{1},\cdots,a_{n})=\sum_{s=1}^{n}(-1)^{s+1}(a_{1},\cdots,\widehat{a_{s}},\cdots,a_{n})$.
This complex equals the shifted complex $(C_{k-1}(E,\mathfrak{M}),d_{k-1})$ in
the dimensions $k\geqslant 1$. Hence its $k$-th homology groups are isomorphic
to $H_{k-1}(E,\mathfrak{M})$ for $k\geqslant 2$.

By Proposition 3.6, we obtain
$H_{n}(\Sigma,\Delta{\,\mathbb{Z}})\cong{\,\mathbb{Z}}^{(p_{n})}\oplus
H_{n}(\Sigma,{\,\mathbb{Z}}[x_{0}])$ for all $n\geqslant 0$. The required
assertion follows from $H_{n}(\Sigma,{\,\mathbb{Z}}[x_{0}])\cong
H_{n-1}(E,\mathfrak{M})$ for all $n\geqslant 2$. ${\Box}$

Any asynchronous transition system may be considered as a pair
$T=(\Sigma,s_{0})$ of its nondegenerate state space $\Sigma$ with an initial
state $s_{0}\in S$. Each morphism between asynchronous transition systems
$(\Sigma,s_{0})\rightarrow(\Sigma^{\prime},s_{0}^{\prime})$ may be given by a
morphism of state spaces $(\sigma,\eta):\Sigma\rightarrow\Sigma^{\prime}$ such
that $\sigma(s_{0})=s_{0}^{\prime}$.

Let $T=(\Sigma,s_{0})$ be an asynchronous transition system with a state space
$\Sigma=(S,E,I,{\rm Tran\,})$. Events $e_{j}\in E$, $j\in J$, are caled
mutually independent if $(e_{j},e_{j^{\prime}})\in I$ for all $j,j^{\prime}\in
J$ such those $j\not=j^{\prime}$. A state $s\in S\sqcup\\{\star\\}$ is
available if there exists $\mu\in M(E,I)$ such that $s_{0}\cdot\mu=s$. The set
of available states is denoted by $S(s_{0})$. The monoid $M(E,I)$ will act on
the set of the available states. Suppose that $T(s_{0})$ is the state space
whose set of states equals $S(s_{0})$.

Define homology groups of space of available states by
$H_{n}(K_{*}(T(s_{0})),\Delta{\,\mathbb{Z}})$. Applying Theorem 3.3, we get
the following.

###### Corollary 3.9

Suppose that an asynchronous transition system $T=(\Sigma,s_{0})$ does not
contain infinite subsets of mutually independent events. Let
$\Sigma=(S,E,I,{\rm Tran\,})$ be its the state space. Suppose that the set $E$
is totally ordered. Then $H_{n}(K_{*}(T(s_{0})),\Delta{\,\mathbb{Z}})$ are
isomorphic to homology groups of the complex

$0\leftarrow\bigoplus\limits_{s\in
S(s_{0})}{\,\mathbb{Z}}\stackrel{{\scriptstyle
d_{1}}}{{\longleftarrow}}\bigoplus\limits_{(s,e_{1})\in S\times
E_{1}}{\,\mathbb{Z}}\stackrel{{\scriptstyle
d_{2}}}{{\longleftarrow}}\bigoplus\limits_{{(s,e_{1},e_{2})\in S\times
E_{2}}}{\,\mathbb{Z}}\leftarrow\cdots\\\
\cdots~{}~{}\leftarrow\bigoplus\limits_{(s,e_{1},\cdots,e_{n-1})\in S\times
E_{n-1}}{\,\mathbb{Z}}\stackrel{{\scriptstyle
d_{n}}}{{\longleftarrow}}\bigoplus\limits_{(s,e_{1},\cdots,e_{n})\in S\times
E_{n}}{\,\mathbb{Z}}\leftarrow\cdots~{}$ (5)

where $E_{n}$ consists of tuples $e_{1}<\cdots<e_{n}$ of mutually commuting
elements of $E$ with

$d_{n}(s,e_{1}\cdots e_{n})=\sum_{i=1}^{n}(-1)^{i}\left((s\cdot
e_{i},e_{1},\cdots,\widehat{e_{i}},\cdots,e_{n})-(s,e_{1},\cdots,\widehat{e_{i}},\cdots,e_{n})\right)$

If the cardinal numbers of mutually independent events is bounded above by a
natural number, then this comlex has a finite length.

##  4 Concluding remarks

Let $\Sigma=(S,E,I,Tran)$ be a state space. Consider the full subcategory
$K(\Sigma)\subset K_{*}(\Sigma)$ whose objects are elements $s\in S$. In [5],
it was studied homology groups of the category $K(\Sigma)$. It was built an
algorithm of computing the first integer homology group of this category and
applied for the calculation of homology groups of finite Petri CE nets. An
algorithm of computing all integer homology groups of finite Petri CE nets is
not found [5, Open Problem 1]. We put forward a conjecture whose confirmation
would be to solve this problem. Let $Q_{*}^{\prime}(U\circ\Sigma)\subseteq
Q_{*}(U\circ\Sigma)$ be a semicubical subset consisting of sets

$Q_{n}^{\prime}(U\circ\Sigma)=\\{(s,e_{1},\cdots,e_{n})\in
Q_{n}(U\circ\Sigma):se_{1}\cdots e_{n}\not=\star\\}$

Consider any functor $F:K(\Sigma)\rightarrow Ab$. Extend it to $K_{*}(\Sigma)$
by $F(\star)=0$.

###### Conjecture 2

Let $\Sigma=(S,E,I,Tran)$ be a state space. If the monoid $M(E,I)$ is locally
finite-dimensional, then for all integer $n\geqslant 0$, the groups
$\underrightarrow{\lim}_{n}^{K(\Sigma)}F$ are isomorphic to $n$-th homology
groups of the complex consisting of groups
$\bigoplus\limits_{(s,e_{1},\cdots,e_{n})\in
Q^{\prime}_{n}(U\circ\Sigma)}F(s)$ and differentials given by
$d_{n}(s,e_{1},\cdots,e_{n},f)=$

$\sum_{i=1}^{n}(-1)^{i}((s\cdot
e_{i},e_{1},\cdots,\widehat{e_{i}},\cdots,e_{n},F(s\stackrel{{\scriptstyle
e_{i}}}{{\rightarrow}}s\cdot a_{i})(f))\\\
-(s,e_{1},\cdots,\widehat{e_{i}},\cdots,e_{n},f))$

## References

  * [1] Nielsen M., Winskel G.,  “Petri nets and bisimulation”,  Theoretical Computer Science, 153:1-2, 1996, 211–244
  * [2] Shields M.W.,  “Concurrent machines”,  Computer Journal, 28 (1985), 449–465
  * [3] Bednarczyk M. A.,  Categories of Asynchronous Systems,  Ph.D. thesis, University of Sussex, report 1/88, 1988; http://www.ipipan.gda.pl/$~{}\widetilde{~{}}$marek
  * [4] Husainov A. A., Tkachenko V. V.,  “Homology groups of asynchronous transition systems”,  Mathematical modeling and the near questions of mathematics. Collection of the scientifics works., KhGPU, Khabarovsk, 2003, 23–33 (Russian)
  * [5] Husainov A.,  “On the homology of small categories and asynchronous transition systems”,  Homology Homotopy Appl., 6:1 (2004), 439–471; http://www.rmi.acnet.ge/hha
  * [6] Goubault E.,  The Geometry of Concurrency,  Ph.D. Thesis, Ecole Normale Supérieure, 1995; http://www.dmi.ens.fr/$~{}\widetilde{~{}}$goubault
  * [7] Gaucher P.,  “About the globular homology of higher dimensional automata”,  Cah. Topol. Geom. Differ., 43:2, 2002, 107–156
  * [8] Khusainov A.A., Lopatkin V.E., Treshchev I.A.,  “Algebraic topology approach to mathematical model analysis of concurrent computational processes”,  Sibirskiĭ Zhurnal Industrial noĭ Matematiki, 11:1 (2008), 141–152 (Russian)
  * [9] Polyakova L.Yu.,  “Resolutions for free partially commutative monoids”,  Sib. Math. J., 48:6 (2007), 1038–1045; translation from Sib. Mat. Zh., 48:6 (2007), 1295–1304
  * [10] Khusainov A.A.,  “Homology groups of semicubical sets”,  Sib. Math. J., 49:1 (2008), 180–190; translation from Sib. Mat. Zh., 49:1 (2008), 224–237
  * [11] Kaczynski T., Mischaikov K., Mrozek M.,  Computational homology,  Springer-Verlag, New York, 2004, (Appl. Math. Sci.; 157)
  * [12] Gabriel P., Zisman M.,  Calculus of Fractions and Homotopy Theory  [Russian translation], Moscow, Mir, 1971
  * [13] MacLane S.,  Categories for the Working Mathematician, Springer-Verlag, Berlin, 1971
  * [14] Oberst U.,  “Homology of categories and exactness of direct limits”,  Math. Z., 107 (1968), 87–115
  * [15] Husainov A. A.,  “On the Leech dimension of a free partially commutative monoid”,  Tbilisi Math. J., 1:1 (2008), 71–87; http://ncst.org.ge/Journals/TMJ/index.html
  * [16] Kaczynski T., Mischaikov K., Mrozek M.,  “Computational homology”,  Homology Homotopy Appl., 5:2 (2003), 233 – 256
  * [17] Baues H.-J., Wirsching G.,  “Cohomology of small categories”,  J. Pure Appl. Algebra, 38:2-3 (1985), 187–211
  * [18] Diekert V., Métivier Y.,  “Partial Commutation and Traces”,  Handbook of formal languages, 3, Springer-Verlag, New York, 1997, 457–533


# Hamiltonian properties in generalized lexicographic products

Jan Ekstein Department of Mathematics and European Centre of Excellence NTIS -
New Technologies for the Information Society, Faculty of Applied Sciences,
University of West Bohemia, Pilsen, Technická 8, 306 14 Plzeň, Czech Republic
e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>Jakub Teska 11footnotemark: 1

###### Abstract

The lexicographic product $G[H]$ of two graphs $G$ and $H$ is obtained from
$G$ by replacing each vertex with a copy of $H$ and adding all edges between
any pair of copies corresponding to adjacent vertices of $G$. We generalize
the lexicographic product such that we replace each vertex of $G$ with
arbitrary graph on the same number of vertices. We present sufficient and
necessary conditions for traceability, hamiltonicity and hamiltonian
connectivity of $G[H]$ if $G$ is a path.

Keywords: lexicographic products, hamiltonian cycles and paths

2010 Mathematics Subject Classification: 05C76, 05C45

##  1 Introduction

The lexicographic product $G[H]$ of two graphs $G$ and $H$ is defined by
$V(G[H])=V(G)\times V(H)$ and
$E(G[H])=\\{(g,h)(g^{\prime},h^{\prime});gg^{\prime}\in E(G)\mbox{ or
}g=g^{\prime}\wedge hh^{\prime}\in E(H)\\}$. In other words the lexicographic
product $G[H]$ of two graphs $G$ and $H$ is obtained from $G$ by replacing
each vertex with a copy of $H$ and adding all edges between any pair of copies
corresponding to adjacent vertices of $G$. Hamiltonian cycles and paths in
lexicographic products have been studied in [2], [3], and [4].

Clearly $G[H]$ contains a cycle of length 3 if both of $G$, $H$ contain at
least one edge. Kaiser and Kriesell proved in [2] that concepts of
pancyclicity and hamiltonicity coincide in the case of lexicographic products
of graphs with at least one edge. Recall that the graph $G$ is weakly
pancyclic or pancyclic, if it either has no cycles, or it contains cycles of
every length between the length of a shortest cycle and that of a longest one,
hamiltonian, respectively.

######  Theorem 1.

__[_2]_ If $G$, $H$ are graphs with at least one edge each, then $G[H]$ is
weakly pancyclic.

In this paper we introduce new concept of the lexicographic product.
Basically, we generalize the lexicographic product by defining the graph
$G[H_{1},H_{2},...,H_{m}]$, which will be a graph like a lexicographic product
with the difference that every vertex of $G$ can be replaced by a different
graph $H_{i}$ on the same number of vertices, $i=1,2,...,m$.

######  Definition 2.

Let $G$ be a graph with $V(G)=\\{u_{1},u_{2},...,u_{m}\\}$ and $H_{i}$ be an
arbitrary graph such that $|H_{i}|=n$ for every $i=1,2,...m$. The _generalized
lexicographic product_ $G[H_{1},H_{2},...,H_{m}]$ of a graph $G$ and
$H_{1},H_{2},...,H_{m}$ is obtained from $G$ by replacing each vertex $u_{i}$
with the graph $H_{i}$ and adding all edges between graphs $H_{i}$ and $H_{j}$
if the corresponding vertices $u_{i}$, $u_{j}$ are adjacent in $G$.

Main results of this paper are the following theorems which generalize and
improve some results from [3].

######  Theorem 3.

Let $P_{2k+1}$ be a path with odd number of vertices, $k\geq 1$. Let
$H_{1},H_{2},...,H_{2k+1}$ be graphs with $n$ vertices. Then the graph
$P_{2k+1}[H_{1},H_{2},...,H_{2k+1}]$ is

  * (i)

hamiltonian if and only if $\pi(H_{1})\geq 1$, $\pi(H_{2k+1})\geq 1$ and
$\sum^{k}_{i=0}\pi(H_{2i+1})\geq n$.

  * (ii)

traceable if and only if $\sum^{k}_{i=0}\pi(H_{2i+1})\geq n-1$.

  * (iii)

hamiltonian connected if and only if $\pi(H_{1})\geq 2$, $\pi(H_{2k+1})\geq 2$
and $\sum^{k}_{i=0}\pi(H_{2i+1})\geq n+1$.

######  Theorem 4.

Let $P_{2k}$ be a path with even number of vertices, $k\geq 1$. Let
$H_{1},H_{2},...,H_{2k}$ be graphs with $n$ vertices. Then the graph
$P_{2k}[H_{1},H_{2},...,H_{2k}]$ is

  * (i)

hamiltonian if and only if $\pi(H_{1})\geq 1$ and $\pi(H_{2k})\geq 1$.

  * (ii)

traceable.

  * (iii)

hamiltonian connected if and only if

    * $\bullet$

$\pi(H_{1})\geq 1$ and $\pi(H_{2k})\geq 1$ for $k=1$.

    * $\bullet$

$\pi(H_{1})\geq 2$ and $\pi(H_{2})\geq 2$ for $k>1$.

Observe that Theorem 3 and Theorem 4 give a complete characterization of
hamiltonicity of $P_{n}[H]$, traceability of $P_{n}[H]$, and hamiltonian
connectivity of $P_{n}[H]$.

##  2 Preliminaries

As for standard terminology, we refer to the book by Bondy and Murty [1].
However, before proving Theorem 3 and Theorem 4 we mention several concepts
and results which we need to make use of.

For a multigraph $G$ and $x,y\in V(G)$ let $[x,y]_{G}$ be the set of edges
between $x$ and $y$ and let $m_{G}(xy)=|[x,y]_{G}|$ be the multiplicity of the
edge $xy$ in $G$. In particular, $\ell_{G}(x)=|[x,x]_{G}|$ denotes the number
of loops at $x$ and $\ell(G)=max\\{\ell_{G}(x):x\in V(G)\\}$. Note that the
degree of a vertex $x$ denoted by $d_{G}(x)=\sum_{y\in
V(G)}m_{G}(xy)+2\ell_{G}(x)$. A multigraph $G$ is $k$ regular if $d_{G}(x)=k$
for every vertex $x$ in $V(G)$. Moreover, let $|G|=|V(G)|$ and $||G||=|E(G)|$.
For any $X\subseteq V(G)$, let $G(X)$ be the submultigraph induced by $X$.

A multigraph $G^{\prime}$ is said to be a multiple of a graph $G$ if
$V(G^{\prime})=V(G)$ and for all $x\neq y\in V(G)$, $m_{G^{\prime}}(xy)>0$
holds only if $xy\in E(G)$. This means, that from a given graph $G$ we can
obtain a multiple $G^{\prime}$ by adding loops or by replacing a single edge
in $G$ by an arbitrary number of edges.

For a given graph $G$ we define $\pi(G)$ to be the maximum number of edges of
a spanning linear forest of $G$ (a forest is linear if its components are
paths).

In [3] Kriesell proved that $G[H]$ is hamiltonian if $G$ has a connected,
$k$-regular multiple with additional properties.

######  Theorem 5.

__[_3]_ Let $G$ and $H$ be graphs. If $G$ has a connected, $2|H|$-regular
multiple $G^{\prime}$ satisfying $\pi(H)\geq\ell_{G^{\prime}}(x)$ for all
$x\in V(G^{\prime})$ then $G[H]$ contains a hamiltonian cycle that contains
exactly $m_{G^{\prime}}(xy)$ edges between $V(G(\\{x\\})[H])$ and
$V(G(\\{y\\})[H])$ for all $x\neq y$ in $V(G)$.

By a _$uv$ -path_ we mean a path from $u$ to $v$ in $G$. If a $uv$-path is
hamiltonian, we call it a _$uv$ -hamiltonian path_. The graph $G$ is
traceable, if $G$ contains a hamiltonian path. The graph $G$ is hamiltonian
connected, if every two vertices of $G$ are connected by a hamiltonian path.

Teichert in [4] and also Kriesell as corollary of Theorem 5 in [3] proved the
following.

######  Theorem 6.

_([3],[4])_ Let $G$ and $H$ be graphs, $|G|\geq 2$. Suppose that $G$ contains
a hamiltonian path.

  * (i)

If $|G|$ is even, then $G[H]$ is traceable.

  * (ii)

If $|G|$ is even and $||H||\geq 1$, then $G[H]$ is hamiltonian.

  * (iii)

If $|G|$ is odd and $\frac{|H|-1}{2}\leq\pi(H)$, then $G[H]$ is traceable.

  * (iv)

If $|G|$ is odd and $\frac{|H|}{2}\leq\pi(H)$, then $G[H]$ is hamiltonian.

Note that the first two statements are in some sense necessary. Let $G$ be
only a path with $n$ vertices, i.e. $G=P_{n}$. Clearly $P_{2}[H]$ is
hamiltonian. If $n\geq 4$ is even, then $P_{n}[H]$ is hamiltonian if and only
if $||H||\geq 1$ because if $H$ has no edge, then $P_{n}[H]$ cannot have a
hamiltonian cycle.

But the last two statements are not necessary. For example, take the graph $H$
on 6 vertices with $\pi(H)=2$ (e.g. the graph $H=P_{3}+3K_{1}$), thus this
graph does not satisfy the conditions $(iii)$ and $(iv)$ in previous theorem.
If $G=P_{3}$, then $G[H]$ is neither hamiltonian nor traceable (see the proof
of Theorem 3). But if we instead of $P_{3}$ take $P_{5}$ as a graph $G$, then
$G[H]$ is hamiltonian (see Figure 1, edges of $P_{5}[P_{3}+3K_{1}]$ between
consecutive copies of $H$ are missing for the clarity). For longer odd paths
$G=P_{2k+1}$, $k\geq 3$, the lexicographic product $G[H]$ is also hamiltonian.

Figure 1: Hamiltonian cycle in $P_{5}[P_{3}+3K_{1}]$ (bold edges)

##  3 Proofs

Let $P_{2k+1}$ be a path with odd number of vertices consecutively denoted by
$u_{1},u_{2},....u_{2k+1}$, $k\geq 1$, and edges denoted by $e_{m}$ where
$e_{m}=u_{m}u_{m+1}$, $m=1,2,...,2k$.

_Proof of Theorem 3_

_(i)_ First suppose that $\pi(H_{1})\geq 1$, $\pi(H_{2k+1})\geq 1$ and
$\sum^{k}_{i=0}\pi(H_{2i+1})\geq n$. Clearly we have $n\geq 2$ because of
$\pi(H_{1})\geq 1$. Now we find a connected $2n$-regular multiple of
$P_{2k+1}$, then we prove the hamiltonicity of
$P_{2k+1}[H_{1},H_{2},...,H_{2k+1}]$ similarly as in [3].

We define the number of loops at each vertex $u_{i}$ of multiple $G^{\prime}$
of $P_{2k+1}$. For even vertices $u_{2},u_{4},...,u_{2k}$ we define
$\ell_{G^{\prime}}(u_{2i})=0$, $i=1,...,k$, and for odd vertices
$\ell_{G^{\prime}}(u_{2i+1})=\pi(H_{2i+1})$, $i=0,...,k$. If
$\sum^{k}_{i=0}\pi(H_{2i+1})>n$ (the multiple $G^{\prime}$ has more than $n$
loops), then we remove arbitrary loops from $G^{\prime}$ in such a way that
$\ell_{G^{\prime}}(u_{1})\geq 1$, $\ell_{G^{\prime}}(u_{2k+1})\geq 1$ and
$\sum^{k}_{i=0}\ell_{G^{\prime}}(u_{2i+1})=n$. Note that
$\ell_{G^{\prime}}(u_{j})\leq\pi(H_{j})$ for $j=1,...,2k+1$.

Now we define the multiplicity of every edge $e_{m}$ of $P_{2k+1}$,
$m=1,2,...2k$,

$m_{G^{\prime}}(e_{1})=2n-2\ell_{G^{\prime}}(u_{1})\hskip
42.67912ptm_{G^{\prime}}(e_{2})=2\ell_{G^{\prime}}(u_{1})$
$m_{G^{\prime}}(e_{3})=2n-2\ell_{G^{\prime}}(u_{1})-2\ell_{G^{\prime}}(u_{3})\hskip
42.67912ptm_{G^{\prime}}(e_{4})=2\ell_{G^{\prime}}(u_{1})+2\ell_{G^{\prime}}(u_{3})$
$m_{G^{\prime}}(e_{5})=2n-2\ell_{G^{\prime}}(u_{1})-2\ell_{G^{\prime}}(u_{3})-2\ell_{G^{\prime}}(u_{5})\hskip
42.67912ptm_{G^{\prime}}(e_{6})=2\ell_{G^{\prime}}(u_{1})+2\ell_{G^{\prime}}(u_{3})+2\ell_{G^{\prime}}(u_{5})$

in general we have:

$m_{G^{\prime}}(e_{2i})=\sum^{i}_{j=1}2\ell_{G^{\prime}}(u_{2j-1})\hskip
42.67912ptm_{G^{\prime}}(e_{2i-1})=2n-\sum^{i}_{j=1}2\ell_{G^{\prime}}(u_{2j-1}),\hskip
14.22636pti=1,2,...k.$

Clearly by the construction, the multiplicity of every edge is at least 2, and
the degree of every vertex $u_{1},u_{2},...,u_{2k}$ is exactly $2n$ and for
the last vertex of our path we have:

$d_{G^{\prime}}(u_{2k+1})=2\ell_{G^{\prime}}(u_{2k+1})+m_{G^{\prime}}(e_{2k})=2\ell_{G^{\prime}}(u_{2k+1})+\sum^{k}_{j=1}2\ell_{G^{\prime}}(u_{2j-1})=2\sum^{k}_{i=0}\ell_{G^{\prime}}(u_{2i+1})=2n.$

Now we prove that $P_{2k+1}[H_{1},H_{2},...,H_{2k+1}]$ contains a hamiltonian
cycle using exactly $\ell_{G^{\prime}}(u_{i})$ edges of $H_{i}$ and exactly
$m_{G^{\prime}}(e_{j})$ edges between $V(P_{2k+1}(\\{u_{j}\\})[H_{j}])$ and
$V(P_{2k+1}(\\{u_{j+1}\\})[H_{j+1}])$ for $i=1,2,...,2k+1$, $j=1,2,...,2k$.

For every vertex $u_{i}$ and every graph $H_{i}$ there exists a spanning
linear subforest of $P_{2k+1}(\\{u_{i}\\})[H_{i}]\cong H_{i}$ with components
$P_{1}(u_{i}),...,P_{j_{i}}(u_{i})$ satisfying

$j_{i}=|H_{i}|-\ell_{G^{\prime}}(u_{i})\hskip 14.22636pt\mbox{ and }\hskip
14.22636pt\sum^{j_{i}}_{t=1}||P_{t}(u_{i})||=\ell_{G^{\prime}}(u_{i}),$

because $\ell_{G^{\prime}}(u_{i})\leq\pi(H_{i})$.

Futhermore after removing all the loops from our multiple $G^{\prime}$, there
exists a closed eulerian trail $C$ in $G^{\prime}$. We obtain the hamiltonian
cycle of $P_{2k+1}[H_{1},H_{2},...,H_{2k+1}]$ as required by replacing
simultaneously the vertices $u_{i}$ at their $t$-th occurence in $C$ by the
component $P_{t}(u_{i})$ for $t=1,2,...,j_{i}$, $i=1,2,...,2k+1$ (for
illustration see Figure 2).

Figure 2: Hamiltonian cycle in $P_{9}[H_{1},H_{2},...,H_{9}]$ from a multiple
$G^{\prime}$

Now suppose that $P_{2k+1}[H_{1},H_{2},...,H_{2k+1}]$ is hamiltonian. If
$||H_{1}||=0$ or $||H_{2k+1}||=0$, then the graph
$P_{2k+1}[H_{1},H_{2},...,H_{2k+1}]$ cannot contain a hamiltonian cycle. Hence
assume that $\pi(H_{1})\geq 1$, $\pi(H_{2k+1})\geq 1$ and
$P_{2k+1}[H_{1},H_{2},...,H_{2k+1}]$ has a hamiltonian cycle $C$. Note that if
$H_{i}$ has at most $\pi(H_{i})$ edges in linear forest, then the number of
components of a linear forest of $H_{i}$ is at least $n-\pi(H_{i})$. Now we
count the number of edges between graphs $H_{1},H_{2},...,H_{2k+1}$ in $C$.

The graph $H_{1}$ has at least $n-\pi(H_{1})$ components, therefore there is
at least $2(n-\pi(H_{1}))$ edges between $H_{1}$ and $H_{2}$ in $C$.

Since $H_{2}$ has only $n$ vertices there is at most $2n$ edges in $C$ from
$H_{2}$. Thus, there is at most $2n-2(n-\pi(H_{1}))=2\pi(H_{1})$ edges between
$H_{2}$ and $H_{3}$ in $C$.

Again $H_{3}$ has at least $n-\pi(H_{3})$ components, therefore there is at
least $2(n-\pi(H_{3}))-2\pi(H_{1})=2n-2\pi(H_{3})-2\pi(H_{1})$ edges between
$H_{3}$ and $H_{4}$ in $C$.

Since $H_{4}$ has only $n$ vertices there is at most $2n$ edges in $C$ from
$H_{4}$. Thus, there is at most
$2n-(2n-2\pi(H_{3})-2\pi(H_{1}))=2\pi(H_{3})+2\pi(H_{1})$ edges between
$H_{4}$ and $H_{5}$ in $C$.

If we continue step by step, we get that between $H_{2k}$ and $H_{2k+1}$ there
is at most $2\pi(H_{2k-1})+2\pi(H_{2k-3})+...+2\pi(H_{3})+2\pi(H_{1})$ edges
in $C$ and from the other side $H_{2k+1}$ has at least $n-\pi(H_{2k+1})$
components, therefore there should be at least $2(n-\pi(H_{2k+1}))$ edges
between $H_{2k+1}$ and $H_{2k}$ in $C$. Now we get that

$2(n-\pi(H_{2k+1}))\leq
2\pi(H_{2k-1})+2\pi(H_{2k-3})+...+2\pi(H_{3})+2\pi(H_{1})$

$n\leq\pi(H_{2k+1})+\pi(H_{2k-1})+\pi(H_{2k-3})+...+\pi(H_{3})+\pi(H_{1})$

$n\leq\sum^{k}_{i=0}\pi(H_{2i+1}).$

Thus we finished the proof of Theorem 3 (i).
$~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\square$

Before the proofs of Theorem 3 statements (ii) and (iii) we define functions
$A(t)$, $B(t)$ and state the following lemmas. Let
$a,b,t\in\\{1,2,...,2k+1\\}$.

$A(t)=0\mbox{ for }t<a;~{}~{}~{}B(t)=0\mbox{ for }t<b;$ $A(t)=1\mbox{ for
}t\geq a;~{}~{}~{}B(t)=1\mbox{ for }t\geq b.$

######  Lemma 7.

Let $P_{2k+1}$ be a path with odd number of vertices, $k\geq 1$,
$a,b\in\\{1,2,...,2k+1\\}$. Let $H_{1},H_{2},...,H_{2k+1}$ be graphs with $n$
vertices such that one of the following conditions holds

  * (I)

$a,b$ are even and $\pi(H_{1})\geq 2$, $\pi(H_{2k+1})\geq 2$ and
$\sum^{k}_{i=0}\pi(H_{2i+1})=n+1$;

  * (II)

$a$ is odd, $b$ is even and $\pi(H_{1})\geq 1$, $\pi(H_{2k+1})\geq 1$ and
$\sum^{k}_{i=0}\pi(H_{2i+1})=n$;

  * (III)

$a,b$ are odd and $\pi(H_{1})\geq 1$, $\pi(H_{2k+1})\geq 1$ and
$\sum^{k}_{i=0}\pi(H_{2i+1})=n-1$;

moreover for $a=1$, $b=2k+1$ we have only $\sum^{k}_{i=0}\pi(H_{2i+1})=n-1$.

Then there exists a connected multiple $G^{\prime}$ of $P_{2k+1}$ such that
$d_{G^{\prime}}(u_{l})=2n$ for $l\in\\{1,2,...,2k+1\\}\setminus\\{a,b\\}$ and
either $d_{G^{\prime}}(u_{a})=d_{G^{\prime}}(u_{b})=2n-1$ if $a\neq b$ or
$d_{G^{\prime}}(u_{a})=2n-2$ if $a=b$.

###### Proof.

(I) $a,b$ are even. We have $n\geq 3$ because of $\pi(H_{1})\geq 2$.

Similarly as in the previous proof, we define the number of loops at each
vertex $u_{i}$ of multiple $G^{\prime}$ of $P_{2k+1}$. For even vertices
$u_{2},u_{4},...,u_{2k}$ we define $\ell_{G^{\prime}}(u_{2i})=0$, $i=1,...,k$,
and for odd vertices $\ell_{G^{\prime}}(u_{2i+1})=\pi(H_{2i+1})$, $i=0,...,k$.
Note that we have $\ell_{G^{\prime}}(u_{1})\geq 2$,
$\ell_{G^{\prime}}(u_{2k+1})\geq 2$ and
$\sum^{k}_{i=0}\ell_{G^{\prime}}(u_{2i+1})=n+1$.

Now we define the multiplicity of every edge $e_{m}$ of $P_{2k+1}$,
$m=1,2,...2k$,

$m_{G^{\prime}}(e_{1})=2n-2\ell_{G^{\prime}}(u_{1})+A(1)+B(1)\hskip
42.67912ptm_{G^{\prime}}(e_{2})=2\ell_{G^{\prime}}(u_{1})-A(2)-B(2)$
$m_{G^{\prime}}(e_{3})=2n-2\ell_{G^{\prime}}(u_{1})-2\ell_{G^{\prime}}(u_{3})+A(3)+B(3)~{}~{}~{}~{}m_{G^{\prime}}(e_{4})=2\ell_{G^{\prime}}(u_{1})+2\ell_{G^{\prime}}(u_{3})-A(4)-B(4)$

in general we have:

$m_{G^{\prime}}(e_{2i})=\sum^{i}_{j=1}2\ell_{G^{\prime}}(u_{2j-1})-A(2i)-B(2i)$
$m_{G^{\prime}}(e_{2i-1})=2n-\sum^{i}_{j=1}2\ell_{G^{\prime}}(u_{2j-1})+A(2i-1)+B(2i-1),\hskip
14.22636pti=1,2,...k.$

Clearly by the construction, the multiplicity of every edge is at least 2 and
the degree of every vertex of $G^{\prime}$ is the following:

$d_{G^{\prime}}(u_{1})=2\ell_{G^{\prime}}(u_{1})+m_{G^{\prime}}(e_{1})=2\ell_{G^{\prime}}(u_{1})+2n-2\ell_{G^{\prime}}(u_{1})+A(1)+B(1)=2n.$

Clearly $A(1)=B(1)=0$.

$d_{G^{\prime}}(u_{2i})=m_{G^{\prime}}(e_{2i-1})+m_{G^{\prime}}(e_{2i})=$
$=2n-\sum^{i}_{j=1}2\ell_{G^{\prime}}(u_{2j-1})+A(2i-1)+B(2i-1)+\sum^{i}_{j=1}2\ell_{G^{\prime}}(u_{2j-1})-A(2i)-B(2i)=$
$=2n+A(2i-1)+B(2i-1)-A(2i)-B(2i),\hskip 14.22636pti=1,2,...k.$

Then $d_{G^{\prime}}(u_{2i})=2n$ for $2i\notin\\{a,b\\}$,
$d_{G^{\prime}}(u_{2i})=2n-1$ for $2i\in\\{a,b\\}$, $a\neq b$, and
$d_{G^{\prime}}(u_{2i})=2n-2$ for $2i=a=b$.

$d_{G^{\prime}}(u_{2i+1})=m_{G^{\prime}}(e_{2i})+m_{G^{\prime}}(e_{2i+1})+2\ell_{G^{\prime}}(u_{2i+1})=$
$=\sum^{i}_{j=1}2\ell_{G^{\prime}}(u_{2j-1})-A(2i)-B(2i)+2n-\sum^{i+1}_{j=1}2\ell_{G^{\prime}}(u_{2j-1})+A(2i+1)+B(2i+1)+2\ell_{G^{\prime}}(u_{2i+1})=$
$=2n-A(2i)-B(2i)+A(2i+1)+B(2i+1)=2n,\hskip 14.22636pti=1,2,...k-1.$

Note that $A(2i)=A(2i+1)$, $B(2i)=B(2i+1)$.

$d_{G^{\prime}}(u_{2k+1})=m_{G^{\prime}}(e_{2k})+2\ell_{G^{\prime}}(u_{2k+1})=\sum^{k+1}_{j=1}2\ell_{G^{\prime}}(u_{2j-1})-A(2k)-B(2k)=$
$=2(n+1)-A(2k)-B(2k)=2n.$

Clearly $A(2k)=B(2k)=1$.

Resulting $G^{\prime}$ is the connected multiple of $P_{2k+1}$ as required.

(II) $a$ is odd and $b$ is even. We have $n\geq 2$ because of $\pi(H_{1})\geq
1$.

We define the number of loops at each vertex $u_{i}$ of multiple $G^{\prime}$
of $P_{2k+1}$ as in (I) such that we have $\ell_{G^{\prime}}(u_{1})\geq 1$,
$\ell_{G^{\prime}}(u_{2k+1})\geq 1$ and
$\sum^{k}_{i=0}\ell_{G^{\prime}}(u_{2i+1})=n$.

Now we define the multiplicity of every edge $e_{m}$ of $P_{2k+1}$,
$m=1,2,...2k$,

$m_{G^{\prime}}(e_{2i})=\sum^{i}_{j=1}2\ell_{G^{\prime}}(u_{2j-1})+A(2i)-B(2i)$
$m_{G^{\prime}}(e_{2i-1})=2n-\sum^{i}_{j=1}2\ell_{G^{\prime}}(u_{2j-1})-A(2i-1)+B(2i-1),\hskip
14.22636pti=1,2,...k.$

Clearly by the construction, the multiplicity of every edge is at least 1 and
the degree of every vertex of $G^{\prime}$ is the following:

$d_{G^{\prime}}(u_{1})=2\ell_{G^{\prime}}(u_{1})+m_{G^{\prime}}(e_{1})=2\ell_{G^{\prime}}(u_{1})+2n-2\ell_{G^{\prime}}(u_{1})-A(1)+B(1)=2n-A(1).$

Clearly $B(1)=0$, $d_{G^{\prime}}(u_{1})=2n$ for $a\neq 1$ and
$d_{G^{\prime}}(u_{1})=2n-1$ for $a=1$.

$d_{G^{\prime}}(u_{2i})=m_{G^{\prime}}(e_{2i-1})+m_{G^{\prime}}(e_{2i})=$
$=2n-\sum^{i}_{j=1}2\ell_{G^{\prime}}(u_{2j-1})-A(2i-1)+B(2i-1)+\sum^{i}_{j=1}2\ell_{G^{\prime}}(u_{2j-1})+A(2i)-B(2i)=$
$=2n-A(2i-1)+B(2i-1)+A(2i)-B(2i)=2n+B(2i-1)-B(2i),\hskip
14.22636pti=1,2,...k.$

Then $A(2i-1)=A(2i)$, $d_{G^{\prime}}(u_{2i})=2n$ for $2i\neq b$ and
$d_{G^{\prime}}(u_{2i})=2n-1$ for $2i=b$.

$d_{G^{\prime}}(u_{2i+1})=m_{G^{\prime}}(e_{2i})+m_{G^{\prime}}(e_{2i+1})+2\ell_{G^{\prime}}(u_{2i+1})=$
$=\sum^{i}_{j=1}2\ell_{G^{\prime}}(u_{2j-1})+A(2i)-B(2i)+2n-\sum^{i+1}_{j=1}2\ell_{G^{\prime}}(u_{2j-1})-A(2i+1)+B(2i+1)+2\ell_{G^{\prime}}(u_{2i+1})=$
$=2n+A(2i)-B(2i)-A(2i+1)+B(2i+1)=2n+A(2i)-A(2i+1),\hskip
14.22636pti=1,2,...k-1.$

Then $B(2i)=B(2i+1)$, $d_{G^{\prime}}(u_{2i+1})=2n$ for $2i+1\neq a$ and
$d_{G^{\prime}}(u_{2i+1})=2n-1$ for $2i+1=a$.

$d_{G^{\prime}}(u_{2k+1})=m_{G^{\prime}}(e_{2k})+2\ell_{G^{\prime}}(u_{2k+1})=\sum^{k+1}_{j=1}2\ell_{G^{\prime}}(u_{2j-1})+A(2k)-B(2k)=$
$=2n+A(2k)-B(2k).$

Clearly $B(2k)=1$, $d_{G^{\prime}}(u_{2k+1})=2n$ for $a\neq 2k+1$ and
$d_{G^{\prime}}(u_{2k+1})=2n-1$ for $a=2k+1$.

Resulting $G^{\prime}$ is the connected multiple of $P_{2k+1}$ as required.

(III) $a,b$ are odd. From $\pi(H_{1})\geq 1$, $\pi(H_{2k+1})\geq 1$ and
$\sum^{k}_{i=0}\pi(H_{2i+1})=n-1$ we have $n>2$.

We define the number of loops at each vertex $u_{i}$ of multiple $G^{\prime}$
of $P_{2k+1}$ as in (I) such that we have $\ell_{G^{\prime}}(u_{1})\geq 1$,
$\ell_{G^{\prime}}(u_{2k+1})\geq 1$, and
$\sum^{k}_{i=0}\ell_{G^{\prime}}(u_{2i+1})=n-1$.

Now we define the multiplicity of every edge $e_{m}$ of $P_{2k+1}$,
$m=1,2,...2k$,

$m_{G^{\prime}}(e_{2i})=\sum^{i}_{j=1}2\ell_{G^{\prime}}(u_{2j-1})+A(2i)+B(2i)$
$m_{G^{\prime}}(e_{2i-1})=2n-\sum^{i}_{j=1}2\ell_{G^{\prime}}(u_{2j-1})-A(2i-1)-B(2i-1),\hskip
14.22636pti=1,2,...k.$

Clearly by the construction, the multiplicity of every edge is at least 2 and
the degree of every vertex of $G^{\prime}$ is the following:

$d_{G^{\prime}}(u_{1})=2\ell_{G^{\prime}}(u_{1})+m_{G^{\prime}}(e_{1})=2\ell_{G^{\prime}}(u_{1})+2n-2\ell_{G^{\prime}}(u_{1})-A(1)-B(1)=2n-A(1)-B(1).$

Then $d_{G^{\prime}}(u_{1})=2n$ for $1\notin\\{a,b\\}$,
$d_{G^{\prime}}(u_{1})=2n-1$ for $1\in\\{a,b\\}$, $a\neq b$, and
$d_{G^{\prime}}(u_{1})=2n-2$ for $1=a=b$.

$d_{G^{\prime}}(u_{2i})=m_{G^{\prime}}(e_{2i-1})+m_{G^{\prime}}(e_{2i})=$
$=2n-\sum^{i}_{j=1}2\ell_{G^{\prime}}(u_{2j-1})-A(2i-1)-B(2i-1)+\sum^{i}_{j=1}2\ell_{G^{\prime}}(u_{2j-1})+A(2i)+B(2i)=$
$=2n-A(2i-1)-B(2i-1)+A(2i)+B(2i)=2n,\hskip 14.22636pti=1,2,...k.$

Note that $A(2i-1)=A(2i)$, $B(2i-1)=B(2i)$.

$d_{G^{\prime}}(u_{2i+1})=m_{G^{\prime}}(e_{2i})+m_{G^{\prime}}(e_{2i+1})+2\ell_{G^{\prime}}(u_{2i+1})=$
$=\sum^{i}_{j=1}2\ell_{G^{\prime}}(u_{2j-1})+A(2i)+B(2i)+2n-\sum^{i+1}_{j=1}2\ell_{G^{\prime}}(u_{2j-1})-A(2i+1)-B(2i+1)+2\ell_{G^{\prime}}(u_{2i+1})=$
$=2n+A(2i)+B(2i)-A(2i+1)-B(2i+1),\hskip 14.22636pti=1,2,...k-1.$

Then $d_{G^{\prime}}(u_{2i+1})=2n$ for $2i+1\notin\\{a,b\\}$,
$d_{G^{\prime}}(u_{2i+1})=2n-1$ for $2i+1\in\\{a,b\\}$, $a\neq b$, and
$d_{G^{\prime}}(u_{2i+1})=2n-2$ for $2i+1=a=b$.

$d_{G^{\prime}}(u_{2k+1})=m_{G^{\prime}}(e_{2k})+2\ell_{G^{\prime}}(u_{2k+1})=\sum^{k+1}_{j=1}2\ell_{G^{\prime}}(u_{2j-1})+A(2k)+B(2k)=$
$=2(n-1)+A(2k)+B(2k)=2n-2+A(2k)+B(2k).$

Then $d_{G^{\prime}}(u_{2k+1})=2n$ for $2k+1\notin\\{a,b\\}$,
$d_{G^{\prime}}(u_{2k+1})=2n-1$ for $2k+1\in\\{a,b\\}$, $a\neq b$, and
$d_{G^{\prime}}(u_{2k+1})=2n-2$ for $2k+1=a=b$.

Let $a=1$, $b=2k+1$. From $\sum^{k}_{i=0}\pi(H_{2i+1})=n-1$ we have $n\geq 1$
and again we define the number of loops at each vertex $u_{i}$ of multiple
$G^{\prime}$ of $P_{2k+1}$ as in (I) such that
$\sum^{k}_{i=0}\ell_{G^{\prime}}(u_{2i+1})=n-1$. Clearly $A(j)=1$ for
$j=1,2,...,2k+1$, $B(j)=0$ for $j=1,2,...,2k$ and $B(2k+1)=1$.

As in general case we define specifically the multiplicity of every edge
$e_{m}$ of $P_{2k+1}$, $m=1,2,...2k$,

$m_{G^{\prime}}(e_{2i})=\sum^{i}_{j=1}2\ell_{G^{\prime}}(u_{2j-1})+1$
$m_{G^{\prime}}(e_{2i-1})=2n-\sum^{i}_{j=1}2\ell_{G^{\prime}}(u_{2j-1})-1,\hskip
14.22636pti=1,2,...k.$

Clearly by the construction, the multiplicity of every edge is at least 1 and
the degree of every vertex of $G^{\prime}$ is the following:

$d_{G^{\prime}}(u_{1})=2\ell_{G^{\prime}}(u_{1})+m_{G^{\prime}}(e_{1})=2\ell_{G^{\prime}}(u_{1})+2n-2\ell_{G^{\prime}}(u_{1})-1=2n-1.$

$d_{G^{\prime}}(u_{2i})=m_{G^{\prime}}(e_{2i-1})+m_{G^{\prime}}(e_{2i})=$
$=2n-\sum^{i}_{j=1}2\ell_{G^{\prime}}(u_{2j-1})-1+\sum^{i}_{j=1}2\ell_{G^{\prime}}(u_{2j-1})+1=2n,\hskip
14.22636pti=1,2,...k.$

$d_{G^{\prime}}(u_{2i+1})=m_{G^{\prime}}(e_{2i})+m_{G^{\prime}}(e_{2i+1})+2\ell_{G^{\prime}}(u_{2i+1})=$
$=\sum^{i}_{j=1}2\ell_{G^{\prime}}(u_{2j-1})+1+2n-\sum^{i+1}_{j=1}2\ell_{G^{\prime}}(u_{2j-1})-1+2\ell_{G^{\prime}}(u_{2i+1})=2n,\hskip
14.22636pti=1,2,...k-1.$

$d_{G^{\prime}}(u_{2k+1})=m_{G^{\prime}}(e_{2k})+2\ell_{G^{\prime}}(u_{2k+1})=\sum^{k+1}_{j=1}2\ell_{G^{\prime}}(u_{2j-1})+1=2(n-1)+1=2n-1.$

In both cases resulting $G^{\prime}$ is the connected multiple of $P_{2k+1}$
as required. ∎

######  Lemma 8.

Let $P_{2k+1}$ be a path with odd number of vertices, $k\geq 1$,
$a,b\in\\{1,2,...,2k+1\\}$. Let $H_{1},H_{2},...,H_{2k+1}$ be graphs with $n$
vertices. Assume that $P_{2k+1}[H_{1},H_{2},...,H_{2k+1}]$ contains a
hamiltonian path $P$ starting in vertex $x$ from $V(G(\\{u_{a}\\})[H_{a}])$
and ending in a vertex $y$ from $V(G(\\{u_{b}\\})[H_{b}])$.

  * (I)

If $a,b$ are even, then $\sum^{k}_{i=0}\pi(H_{2i+1})\geq n+1$;

  * (II)

If $a$ is odd and $b$ is even, then $\sum^{k}_{i=0}\pi(H_{2i+1})\geq n$;

  * (III)

If $a,b$ are odd, then $\sum^{k}_{i=0}\pi(H_{2i+1})\geq n-1$.

###### Proof.

(I) $a,b$ are even. Clearly $A(1)=B(1)=0$ and $A(2k)=B(2k)=1$.

The graph $H_{1}$ has at least $n-\pi(H_{1})$ components, therefore there is
at least $2(n-\pi(H_{1}))+A(1)+B(1)=2(n-\pi(H_{1}))$ edges between $H_{1}$ and
$H_{2}$ in $P$.

Since $H_{2}$ has only $n$ vertices there is at most $2n$ edges in $P$ from
$H_{2}$. Thus, there is at most
$2n-2(n-\pi(H_{1}))-A(2)-B(2)=2\pi(H_{1})-A(2)-B(2)$ edges between $H_{2}$ and
$H_{3}$ in $P$.

In general we have at most

$\sum^{i}_{j=1}2\pi(H_{2j-1})-A(2i)-B(2i),\hskip 14.22636pti=1,2,...k,$

edges between $H_{2i}$ and $H_{2i+1}$ in $P$ and we have at least

$2n-\sum^{i}_{j=1}2\pi(H_{2j-1})+A(2i-1)+B(2i-1),\hskip 14.22636pti=1,2,...k,$

edges between $H_{2i-1}$ and $H_{2i}$ in $P$.

The last subgraph $H_{2k+1}$ has $n-\pi(H_{2k+1})$ components in its path
covering. Therefore there is at least $2(n-\pi(H_{2k+1}))$ edges between
$H_{2k+1}$ and $H_{2k}$ in $P$. Thus we get:

$2(n-\pi(H_{2k+1}))\leq\sum^{k}_{j=1}2\pi(H_{2j-1})-A(2k)-B(2k)\leq\sum^{k}_{j=1}2\pi(H_{2j-1})-2$

$2n+A(2k)+B(2k)=2n+2\leq\sum^{k}_{j=0}2\pi(H_{2j+1})$

$n+1\leq\sum^{k}_{j=0}\pi(H_{2j+1}).$

(II) $a$ is odd and $b$ is even. Clearly $B(1)=0$ and $B(2k)=1$.

Similarly as in (I), we have at most

$\sum^{i}_{j=1}2\pi(H_{2j-1})+A(2i)-B(2i),\hskip 14.22636pti=1,2,...k,$

edges between $H_{2i}$ and $H_{2i+1}$ in $P$ and we have at least

$2n-\sum^{i}_{j=1}2\pi(H_{2j-1})-A(2i-1)+B(2i-1),\hskip 14.22636pti=1,2,...k,$

edges between $H_{2i-1}$ and $H_{2i}$ in $P$.

The last subgraph $H_{2k+1}$ has $n-\pi(H_{2k+1})$ components in its path
covering. Therefore there is at least $2(n-\pi(H_{2k+1}))-A(2k+1)+A(2k)$ edges
between $H_{2k+1}$ and $H_{2k}$ in $P$. Clearly $A(2k+1)=1$. Thus we get:

$2(n-\pi(H_{2k+1}))-A(2k+1)+A(2k)\leq\sum^{k}_{j=1}2\pi(H_{2j-1})+A(2k)-B(2k)$

$2n-A(2k+1)+B(2k)=2n\leq\sum^{k}_{j=0}2\pi(H_{2j+1})$

$n\leq\sum^{k}_{j=0}\pi(H_{2j+1}).$

(III) $a,b$ are odd.

Again similarly as in (I), we have at most

$\sum^{i}_{j=1}2\pi(H_{2j-1})+A(2i)+B(2i),\hskip 14.22636pti=1,2,...k,$

edges between $H_{2i}$ and $H_{2i+1}$ in $P$ and we have at least

$2n-\sum^{i}_{j=1}2\pi(H_{2j-1})-A(2i-1)-B(2i-1),\hskip 14.22636pti=1,2,...k,$

edges between $H_{2i-1}$ and $H_{2i}$ in $P$.

The last subgraph $H_{2k+1}$ has $n-\pi(H_{2k+1})$ components in its path
covering. Therefore, there should be at least
$2(n-\pi(H_{2k+1}))-A(2k+1)+A(2k)-B(2k+1)+B(2k)$ edges between $H_{2k+1}$ and
$H_{2k}$ in $P$. Clearly $A(2k+1)=B(2k+1)=1$. Thus we get:

$2(n-\pi(H_{2k+1}))-A(2k+1)+A(2k)-B(2k+1)+B(2k)\leq\sum^{k}_{j=1}2\pi(H_{2j-1})+A(2k)+B(2k)$

$2n-A(2k+1)-B(2k+1)=2n-2\leq\sum^{k}_{j=0}2\pi(H_{2j+1})$

$n-1\leq\sum^{k}_{j=0}\pi(H_{2j+1}).$

∎

Now we are ready to prove Theorem 3 statements (ii) and (iii).

_(ii)_ First suppose that $\sum^{k}_{i=0}\pi(H_{2i+1})\geq n-1$. Let $x,y$ be
a vertex in $H_{1},H_{2k+1}$ such that $x,y$ is not a vertex of degree 2 in
some component (path) of a spanning linear forest of $H_{1},H_{2k+1}$ with
$\pi(H_{1}),\pi(H_{2k+1})$ edges, respectively. We show that
$P_{2k+1}[H_{1},H_{2},...,H_{2k+1}]$ contains an $xy$-hamiltonian path.

We set $a=1$ and $b=2k+1$. By Lemma 7 (III) we find a connected multiple
$G^{\prime}$ of $P_{2k+1}$ such that $d_{G^{\prime}}(u_{l})=2n$ for
$l\in\\{2,3,...,2k\\}$ and
$d_{G^{\prime}}(u_{1})=d_{G^{\prime}}(u_{2k+1})=2n-1$. Note that if
$\sum^{k}_{i=0}\pi(H_{2i+1})>n-1$ (the multiple $G^{\prime}$ has more than
$n-1$ loops), then we remove arbitrary loops from $G^{\prime}$ in such a way
that $\sum^{k}_{i=0}\ell_{G^{\prime}}(u_{2i+1})=n-1$. Clearly
$\ell_{G^{\prime}}(u_{j})\leq\pi(H_{j})$ for $j=1,...,2k+1$.

As before, we prove that $P_{2k+1}[H_{1},H_{2},...,H_{2k+1}]$ contains a
$xy$-hamiltonian path using exactly $\ell_{G^{\prime}}(u_{i})$ edges of
$H_{i}$ and exactly $m_{G^{\prime}}(e_{j})$ edges between
$V(P_{2k+1}(\\{u_{j}\\})[H_{j}])$ and $V(P_{2k+1}(\\{u_{j+1}\\})[H_{j+1}])$
for $i=1,2,...,2k+1$, $j=1,2,...,2k$.

For every vertex $u_{i}$ and every graph $H_{i}$ there exists a spanning
linear subforest of $P_{2k+1}(\\{u_{i}\\})[H_{i}]\cong H_{i}$ with components
$P_{1}(u_{i}),...,P_{j_{i}}(u_{i})$ satisfying

$j_{i}=|H_{i}|-\ell_{G^{\prime}}(u_{i})\hskip 14.22636pt\mbox{ and }\hskip
14.22636pt\sum^{j_{i}}_{t=1}||P_{t}(u_{i})||=\ell_{G^{\prime}}(u_{i}),$

because $\ell_{G^{\prime}}(u_{i})\leq\pi(H_{i})$.

Futhermore after removing all the loops from multiple $G^{\prime}$, there
exists an open eulerian trail $C$ in $G^{\prime}$ from $u_{1}$ to $u_{2k+1}$
of $P_{2k+1}$. We obtain the $xy$-hamiltonian path $P$ in
$P_{2k+1}[H_{1},H_{2},...,H_{2k+1}]$ as required by replacing simultaneously
the vertices $u_{i}$ at their $t$-th occurence in $C$ by the component
$P_{t}(u_{i})$ for $t=1,2,...,j_{i}$, $i=1,2,...,2k+1$ such that $x$ is the
first vertex and $y$ is the last vertex of $P$. Note that $x,y$ are
endvertices of different paths $P_{t}(u_{i})$ or isolated vertices.

Now suppose that $P_{2k+1}[H_{1},H_{2},...,H_{2k+1}]$ contains some
hamiltonian path $P$. We may assume that the hamiltonian path starts in
$H_{1}$ and ends in $H_{2k+1}$. By Lemma 8 (III) we get that
$\sum^{k}_{i=0}\pi(H_{2i+1})\geq n-1.$

$~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\square$

_(iii)_ First suppose that $\pi(H_{1})\geq 2$, $\pi(H_{2k+1})\geq 2$ and
$\sum^{k}_{i=0}\pi(H_{2i+1})\geq n+1$. Let $x,y$ be a vertex in $H_{a},H_{b}$,
$a,b\in\\{1,2,...,2k+1\\}$, respectively. We show that
$P_{2k+1}[H_{1},H_{2},...,H_{2k+1}]$ contains an $xy$-hamiltonian path for
every $x,y$.

Suppose that $a,b$ are even. By Lemma 7 (I) we find a connected multiple
$G^{\prime}$ of $P_{2k+1}$ such that $d_{G^{\prime}}(u_{l})=2n$ for
$l\in\\{1,2,...,2k+1\\}\setminus\\{a,b\\}$ and either
$d_{G^{\prime}}(u_{a})=d_{G^{\prime}}(u_{b})=2n-1$ if $a\neq b$ or
$d_{G^{\prime}}(u_{a})=2n-2$ if $a=b$. Note that if
$\sum^{k}_{i=0}\pi(H_{2i+1})>n+1$ (the multiple $G^{\prime}$ has more than
$n+1$ loops), then we remove arbitrary loops from $G^{\prime}$ in such a way
that $\ell_{G^{\prime}}(u_{1})\geq 2$, $\ell_{G^{\prime}}(u_{2k+1})\geq 2$ and
$\sum^{k}_{i=0}\ell_{G^{\prime}}(u_{2i+1})=n+1$. Clearly
$\ell_{G^{\prime}}(u_{j})\leq\pi(H_{j})$ for $j=1,...,2k+1$.

Suppose that $a$ is odd and $b$ is even (the case $a$ is even and $b$ is odd
is symmetrical). If $x$ is a vertex of degree 2 in some component (path) $P$
of a spanning linear forest of $H_{a}$ with $\pi(H_{a})$ edges, then we remove
one edge of $P$ incident with $x$ from this spanning linear forest. Hence we
have $\pi(H_{1})\geq 1$, $\pi(H_{2k+1})\geq 1$ and
$\sum^{k}_{i=0}\pi(H_{2i+1})\geq n$. By Lemma 7 (II) we find a connected
multiple $G^{\prime}$ of $P_{2k+1}$ such that $d_{G^{\prime}}(u_{l})=2n$ for
$l\in\\{1,2,...,2k+1\\}\setminus\\{a,b\\}$ and
$d_{G^{\prime}}(u_{a})=d_{G^{\prime}}(u_{b})=2n-1$. Note that if
$\sum^{k}_{i=0}\pi(H_{2i+1})>n$ (the multiple $G^{\prime}$ has more than $n$
loops), then we remove arbitrary loops from $G^{\prime}$ in such a way that
$\ell_{G^{\prime}}(u_{1})\geq 1$, $\ell_{G^{\prime}}(u_{2k+1})\geq 1$ and
$\sum^{k}_{i=0}\ell_{G^{\prime}}(u_{2i+1})=n$. Clearly
$\ell_{G^{\prime}}(u_{j})\leq\pi(H_{j})$ for $j=1,...,2k+1$.

Suppose that $a,b$ are odd. We remove at most 2 edges from spanning linear
forests of $H_{a}$ and $H_{b}$ such that now $x$ and $y$ are not vertices of
degree 2 in some component (path) of a spanning linear forest of $H_{a}$ or
$H_{b}$ and $x,y$ are not in the same component (path) of a spaning linear
forest of $H_{a}=H_{b}$. Hence we have $\pi(H_{1})\geq 1$, $\pi(H_{2k+1})\geq
1$ and $\sum^{k}_{i=0}\pi(H_{2i+1})\geq n-1$ even if $a,b$ are in the same
component. By Lemma 7 (III) we find a connected multiple $G^{\prime}$ of
$P_{2k+1}$ such that $d_{G^{\prime}}(u_{l})=2n$ for
$l\in\\{1,2,...,2k+1\\}\setminus\\{a,b\\}$ and either
$d_{G^{\prime}}(u_{a})=d_{G^{\prime}}(u_{b})=2n-1$ if $a\neq b$ or
$d_{G^{\prime}}(u_{a})=2n-2$ if $a=b$. Note that if
$\sum^{k}_{i=0}\pi(H_{2i+1})>n-1$ (the multiple $G^{\prime}$ has more than
$n-1$ loops), then we remove arbitrary loops from $G^{\prime}$ in such a way
that $\ell_{G^{\prime}}(u_{1})\geq 1$, $\ell_{G^{\prime}}(u_{2k+1})\geq 1$ and
$\sum^{k}_{i=0}\ell_{G^{\prime}}(u_{2i+1})=n-1$. Clearly
$\ell_{G^{\prime}}(u_{j})\leq\pi(H_{j})$ for $j=1,...,2k+1$.

Similarly as in the previous proof, we prove that
$P_{2k+1}[H_{1},H_{2},...,H_{2k+1}]$ contains a $xy$-hamiltonian path using
exactly $\ell_{G^{\prime}}(u_{i})$ edges of $H_{i}$ and exactly
$m_{G^{\prime}}(e_{j})$ edges between $V(P_{2k+1}(\\{u_{j}\\})[H_{j}])$ and
$V(P_{2k+1}(\\{u_{j+1}\\})[H_{j+1}])$ for $i=1,2,...,2k+1$, $j=1,2,...,2k$.

For every vertex $u_{i}$ and every graph $H_{i}$ there exists a spanning
linear subforest of $P_{2k+1}(\\{u_{i}\\})[H_{i}]\cong H_{i}$ with components
$P_{1}(u_{i}),...,P_{j_{i}}(u_{i})$ satisfying

$j_{i}=|H_{i}|-\ell_{G^{\prime}}(u_{i})\hskip 14.22636pt\mbox{ and }\hskip
14.22636pt\sum^{j_{i}}_{t=1}||P_{t}(u_{i})||=\ell_{G^{\prime}}(u_{i}),$

because $\ell_{G^{\prime}}(u_{i})\leq\pi(H_{i})$.

Futhermore after removing all the loops from multiple $G^{\prime}$, there
exists an open eulerian trail $C$ in $G^{\prime}$ from $u_{a}$ to $u_{b}$ if
$a\neq b$ and a closed eulerian trail $C$ in $G^{\prime}$ if $a=b$. We obtain
the $xy$-hamiltonian path in $P_{2k+1}[H_{1},H_{2},...,H_{2k+1}]$ as required
by replacing simultaneously the vertices $u_{i}$ at their $t$-th occurence in
$C$ by the component $P_{t}(u_{i})$ for $t=1,2,...,j_{i}$, $i=1,2,...,2k+1$
such that $x$ is the first vertex and $y$ is the last vertex of $P$. Note that
$x,y$ are endvertices of different paths $P_{t}(u_{i})$ or isolated vertices.

Now suppose that $P_{2k+1}[H_{1},H_{2},...,H_{2k+1}]$ is hamiltonian
connected. Clearly, if $\pi(H_{1})\leq 1$, $\pi(H_{2k+1})\leq 1$, then there
is no hamiltonian path starting and ending in $H_{2}$, $H_{2k}$, respectively.
Thus $\pi(H_{1})\geq 2$, $\pi(H_{2k+1})\geq 2$ and $n>2$
($P_{2k+1}[H_{1},H_{2},...,H_{2k+1}]$ has to be 3-connected). Since this graph
has a hamilonian path between two arbitrary vertices, by Lemma 8 we
immediately get that $\sum^{k}_{i=0}\pi(H_{2i+1})\geq n+1.$

$~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\square$

_Proof of Theorem 4_

The proofs of statements (i) and (ii) of Theorem 4 follows immediately from
the proof of Theorem 6 from [3].

_(iii)_ Let $k=1$. If $\pi(H_{1})=0$ or $\pi(H_{2})=0$, then clearly, there is
no hamiltonian path between some vertices of $H_{2}$ or $H_{1}$, respectively.
If $\pi(H_{1})\geq 1$ and $\pi(H_{2k})\geq 1$, then clearly there exists a
hamiltonian path between every two vertices of $P_{2}[H_{1},H_{2}]$.

Let $k>1$. First suppose that $P_{2k}[H_{1},H_{2},...,H_{2k}]$ is hamiltonian
connected. If $\pi(H_{1})\leq 1$ or $\pi(H_{2k})\leq 1$, then clearly, there
is no hamiltonian path between some two vertices of $H_{2}$ or $H_{2k-1}$,
respectively.

Now assume that $\pi(H_{1})\geq 2$ and $\pi(H_{2k})\geq 2$. Let $x$ be a
vertex of $V(P_{2k}(\\{u_{a}\\})[H_{a}])$ and $y$ be a vertex of
$V(P_{2k}(\\{u_{b}\\})[H_{b}])$. We may assume that $a\leq b$. Let $F$ be
1-factor of $P_{2k}$, $S_{1}$ a multigraph with only one vertex $u_{1}$ and
one loop, $S_{2}$ a multigraph with only vertex $u_{2k}$ and one loop, and let
$P^{\prime}\subseteq P_{2k}$ be a path from $u_{a}$ to $u_{b}$ in $P_{2k}$ and
$P^{\prime\prime}\subseteq P_{2k}$ a path from $u_{b}$ to $u_{2k}$ in $P_{2k}$
if any.

  * (I)

Let $b-a$ be odd. Then $P^{\prime}$ is an even path and let $F_{1}$ be
1-factor of $P^{\prime}$ and set $F_{2}=P^{\prime}-E(F_{1})$. Then we define
multiple $G^{\prime}$:

$G^{\prime}=2P_{2k}+(2n-4)F+S_{1}+S_{2}-F_{1}+F_{2}.$

Clearly, the degree of every vertex of $G^{\prime}$ except from $u_{a}$ and
$u_{b}$ is $2n$ and $d_{G^{\prime}}(u_{a})=d_{G^{\prime}}(u_{b})=2n-1$ and the
multiplicity of every edge of $G^{\prime}$ is at least 1.

  * (II)

Let $b-a$ is even. We may assume, that $a$ is odd (otherwise we relabel all
the vertices: $u_{1}\rightarrow u_{2k},u_{2}\rightarrow
u_{2k-1},...,u_{2k}\rightarrow u_{1}$). Let $F_{1}$ be 1-factor of
$P^{\prime}-u_{b}$ and $F_{2}$ be 1-factor of $P^{\prime}-u_{a}$. Since $a$ is
odd, $b$ is odd as well thus $P^{\prime\prime}$ is an even path. Let $F_{3}$
be 1-factor of $P^{\prime\prime}$ and set $F_{4}=P^{\prime\prime}-E(F_{3})$.
Then we define multiple $G^{\prime}$:

$G^{\prime}=2P_{2k}+(2n-4)F+S_{1}+2S_{2}-F_{1}+F_{2}-2F_{3}+2F_{4}.$

Clearly, the degree of every vertex of $G^{\prime}$ except from $u_{a}$ and
$u_{b}$ is $2n$, $d_{G^{\prime}}(u_{a})=d_{G^{\prime}}(u_{b})=2n-1$ if $a\neq
b$, $d_{G^{\prime}}(u_{a})=d_{G^{\prime}}(u_{b})=2n-2$ if $a=b$, and the
multiplicity of every edge of $G^{\prime}$ is at least 1. Note that $n\geq 3$
because of $\pi(H_{1})\geq 2$.

From such a multiple $G^{\prime}$ in both cases we get a hamiltonian path
between two arbitrary vertices of $P_{2k}[H_{1},H_{2},...,H_{2k}]$ similarly
as in the proof of Theorem 3. $\square$

##  4 Next results

Now we easily get results concerning the lexicographic product of $P_{2k+1}$
and given graph $H$.

######  Theorem 9.

Let $P_{2k+1}$ be a path with $2k+1$ vertices, $k\geq 1$, and $H$ be a graph.
Then the lexicographic product $P_{2k+1}[H]$ is pancyclic if and only if
$\pi(H)\geq 1$ and $\lceil\frac{|H|}{\pi(H)}\rceil\leq k+1$.

###### Proof.

Set $H_{1}=...=H_{2k+1}=H$. By Theorem 3 (i), $P_{2k+1}[H]$ is hamiltonian
$\Leftrightarrow$ $\sum^{k}_{i=0}\pi(H_{2i+1})\geq|H|$ $\Leftrightarrow$
$(k+1)\pi(H)\geq|H|$ $\Leftrightarrow$ $\lceil\frac{|H|}{\pi(H)}\rceil\leq
k+1$ because $k+1$ is an integer. The pancyclicity follows from Theorem 1. ∎

######  Theorem 10.

Let $P_{2k+1}$ be a path with $2k+1$ vertices, $k\geq 1$, and $H$ be a graph.
Then the lexicographic product $P_{2k+1}[H]$ is traceable if and only if
$\lceil\frac{|H|-1}{\pi(H)}\rceil\leq k+1$.

###### Proof.

Set $H_{1}=...=H_{2k+1}=H$. By Theorem 3 (ii), $P_{2k+1}[H]$ is traceable
$\Leftrightarrow$ $\sum^{k}_{i=0}\pi(H_{2i+1})\geq|H|-1$ $\Leftrightarrow$
$(k+1)\pi(H)\geq|H|-1$ $\Leftrightarrow$ $\lceil\frac{|H|-1}{\pi(H)}\rceil\leq
k+1$ because $k+1$ is an integer. ∎

######  Corollary 11.

Let $G$ and $H$ be graphs, $|G|\geq 2$. Suppose that $G$ contains a
hamiltonian path.

  * •

If $|G|=2k+1$ and $\frac{|H|}{k+1}\leq\pi(H)$, then $G[H]$ is hamiltonian.

  * •

If $|G|=2k+1$ and $\frac{|H|-1}{k+1}\leq\pi(H)$, then $G[H]$ is traceable.

Thus we improved Theorem 6 and the bounds are the best possible. Moreover we
get a similar result also for hamiltonian connectivity.

######  Theorem 12.

Let $P_{2k+1}$ be a path with $2k+1$ vertices, $k\geq 1$, and $H$ be a graph.
Then the lexicographic product $P_{2k+1}[H]$ is hamiltonian connected if and
only if $\pi(H)\geq 2$ and $\lceil\frac{|H|+1}{\pi(H)}\rceil\leq k+1$.

###### Proof.

Set $H_{1}=...=H_{2k+1}=H$. By Theorem 3 (iii), $P_{2k+1}[H]$ is hamiltonian
connected $\Leftrightarrow$ $\sum^{k}_{i=0}\pi(H_{2i+1})\geq|H|+1$
$\Leftrightarrow$ $(k+1)\pi(H)\geq|H|+1$ $\Leftrightarrow$
$\lceil\frac{|H|+1}{\pi(H)}\rceil\leq k+1$ because $k+1$ is an integer. ∎

######  Corollary 13.

Let $G$ and $H$ be graphs, $|G|\geq 2$. Suppose that $G$ contains a
hamiltonian path.

If $|G|=2k+1$ and $\frac{|H|+1}{k+1}\leq\pi(H)$, then $G[H]$ is hamiltonian
connected.

######  Theorem 14.

Let $P_{2k}$ be a path with $2k$ vertices, $k\geq 1$, and $H$ be a graph. Then
the lexicographic product $P_{2k}[H]$ is hamiltonian connected if and only

  * $\bullet$

$\pi(H)\geq 1$ for $k=1$.

  * $\bullet$

$\pi(H)\geq 2$ for $k>1$.

###### Proof.

Easy corollary of Theorem 4 (iii). ∎

######  Corollary 15.

Let $G$ and $H$ be graphs, $|G|\geq 2$. Suppose that $G$ contains a
hamiltonian path.

  * If $|G|=2$ and $||H||\geq 1$, then $G[H]$ is hamiltonian connected.

  * If $|G|=2k$, for $k>1$, and $||H||\geq 2$, then $G[H]$ is hamiltonian connected.

##  5 Conclusion

In this paper we finished a complete characterization of hamiltonicity
(Theorem 6 and Theorem 9), traceability (Theorem 6 and Theorem 10) and
hamiltonian connectedness (Theorem 12 and Theorem 14) of $G[H]$, where $G$ is
a path. Moreover we prove it for generalized lexicographic products also
defined in this paper.

This work was partly supported by the European Regional Development Fund
(ERDF), project NTIS - New Technologies for Information Society, European
Centre of Excellence, CZ.1.05/1.1.00/02.0090, and by project GA20-09525S of
the Czech Science Foundation.

## References

  * [1] J.A. Bondy, U.S.R. Murty; Graph Theory, Graduate Texts in Mathematics 244; Springer, New York 2008.
  * [2] T. Kaiser, M. Kriesell; On the Pancyclicity of Lexicographic Products; Graphs and Combinatorics 22 (1) (2006), 51-58.
  * [3] M. Kriesell; A Note on Hamiltonian Cycles in Lexicographical Products; Journal of Automata, Languages and Combinatorics 2 (2) (1997), 135-138.
  * [4] H.-M. Teichert; Hamiltonian properties of the lexicographic product of undirected graphs; Elektronische Informationsverarbeitung Kybernetik 19 (1983) 1/2, 67-77.