# Secure Traversable Event logging for Responsible Identification of
Vertically Partitioned Health Data

Sunanda Bose  Simula Research Laboratory
Oslo, Norway
<EMAIL_ADDRESS>Dusica Marijan  Simula Research Laboratory
Oslo, Norway
<EMAIL_ADDRESS>
###### Abstract

We aim to provide a solution for the secure identification of sensitive
medical information. We consider a repository of de-identified medical data
that is stored in the custody of a Healthcare Institution. The identifying
information which is stored separately can be associated with the medical
information only by a subset of users referred to as custodians. This paper
intends to secure the process of associating identifying information with
sensitive medical information. We also enforce the responsibility of the
custodians by maintaining an immutable ledger documenting the events of such
information identification. The paper proposes a scheme for constructing
ledger entries that allow the custodians and patients to browse through the
entries which they are associated with. However, in order to respect their
privacy, such traversal requires appropriate credentials to ensure that a user
cannot gain any information regarding the other users involved in the system
unless they are both involved in the same operation.

###### Index Terms:

Security and Privacy, Healthcare, Accountable private information retrieval

##  I Introduction

Although Health Data (HD) is generally considered private information owned by
patients, it is often stored in the custody of a healthcare institute. HD may
be used for medical research involving researchers inside or outside the
jurisdiction of the institute. The institutes generally anonymize the data
before sending them to researchers working outside the jurisdiction. However,
the institute can also have some researchers working under the jurisdiction of
the institute. The internal researchers may use the data to find out the
incompleteness and inconsistencies in the medical record [1]. Incompleteness
may signify that some documents (e.g. laboratory tests or doctor’s reports)
that are supposed to be in the repository are not yet submitted. If any
inconsistency is spotted by the internal researchers, this may lead to the
decision of repeating some clinical tests or can even identify a misdiagnosis.

National healthcare systems of several countries also maintain documentation
of the population[2][1][3]. These registries comprise different types of
health data, associated with their personal identity numbers [2]. The Cancer
Registries usually collect data from various sources, like hospitals,
clinicians, dentists, laboratories, radiotherapy data, Death Certificates[4].
In [1] and [5], two methods of data collection are suggested. In the passive
method, the institutions send information to the Cancer registries. In the
active method, the staff from the Cancer Registry collects the data from these
institutions. A team of Registry personnel working in the jurisdiction ensures
the quality of the data by checking duplicate entries and validating the
consistency of records. Such teams are typically led by a medically-qualified
Principal Investigator who has a background in epidemiology and/or public
health [1]. These registries maintain a group of internal experts, who
regularly analyze HD stored in their registry [1]. There can be multiple
medical records associated with a patient. This can be considered as a one-to-
many relationship between identifying information and medical information. As
these data contain highly sensitive information, it has to be protected
against adversarial access. Only legitimate users of these data are the
internal experts, referred to as _Custodians_ , who may identify the patient
associated with a medical record.

Hence, we summarize legitimate data access scenarios.

  1. 1.

Identify a patient associated with a record.

  2. 2.

Fetch or insert data associated with a patient.

The custodian performing these operations is gaining significant private
information about the patient. Although the legal framework permits the
custodian to gain that information, it has to be ensured that the gained
information is not used for malicious purposes. However, the events of the
utilization of that information for malicious purposes may only happen after
the event of information gain has happened. In the case of malicious usage,
the events of information gain can be correlated only if those events are
logged. Such an approach can promote the legitimacy of information gain by
ensuring the responsibility of the custodians. Although there have been
research works addressing the security and privacy concerns of private
information storage and retrieval, which is mentioned in Section II, these
works do not address the problem of responsible identification of de-
identified sensitive data.

Therefore, this paper proposes a secure system of storage and retrieval of HD
that can be accessed by custodians with sufficient credentials. As such access
can lead to information gain about the patients, the events of such access are
documented in an immutable ledger which can be securely traversed by the
custodians and the patients with appropriate credentials. However, in order to
design such a solution we have to overcome some technical challenges. The
ledger has to be protected from adversarial access to ensure the privacy of
the custodians as well as the patients. Simultaneously, the legitimate users,
(custodians and the patients) should be permitted to traverse through the
ledger and analyze the events of information gain that relates to them.
Moreover, the supervisor(s) (often termed as Principal Investigator[1]) may
need to access the ledger to correlate the events with some malicious indecent
and verify its legitimacy. We also evaluate our proposed solution in terms of
security and performance.

The paper is organized as follows. A brief summary of existing works related
to our problem is presented in Section II. In section III we formulate the
scientific problem of responsible identification and present the functional
requirements. We present our proposed solution in Section IV. The security and
performance of our proposed solution is evaluated in Section V. Finally,
Section VI concludes the paper.

##  II Related Work

Ensuring the privacy of patients’ sensitive data is an essential requirement
of managing HD [6]. To ensure the confidentiality of HD, authors in [7]
implemented an AT&T-based scheme for access control of medical records. In
[8], the authors describe several access control mechanisms (RBAC, MAC, DAC,
and PBAC) and their applicability for ensuring the privacy of the HD. However,
restricting access to the documents is not our only objective. We want to make
the user responsible for accessing the document. Moreover, encrypted documents
are difficult to search for or analyze. We only need de-identified data that
can be used for knowledge discovery without directly revealing the patient’s
identity.

Threshold cryptosystem has been used in literature [9][10][11] to provide
shared access to health data. Cryptographic access schemes like IBE, CP-ABE
are used in [12], [13] [9] [14]. In [13] medical data is first encrypted by
the sender using the symmetric encryption algorithm AES. The secret key is
encrypted using IBE and shares the encrypted document along with the encrypted
key. In [12] a Hierarchical access scheme is proposed, where the Public Health
Office serves as the Public Key Generator (PKG) at the highest level, and the
Hospitals, and Clinics are at the lower level. The storage servers located at
hospitals and clinics store the medical records of their patients only. The
public storage server is responsible for storing the referral medical records.
In [15] IBE is used along with a Markle Hash Tree to ensure the deletion of
HD.

Our problem also requires the HD to be shared among multiple custodians.
However, our intention is to allow one custodian to access the patients’
records independently without any co-operations from other custodians.

Vertical Partitioning of data is a popular technique of de-identifying data
which is often used along with anonymization. In [16] HD is partitioned into
three tables. One contains the original medical information, without the
identifying attributes. The other two tables contain anonymized quasi-
identifiable111The attributes that can reveal important information about the
identity of the patient when correlated with publicly available information.
attributes and encrypted ciphertexts of identifying and quasi-identifiable
attributes. Different healthcare institutions may maintain records as
vertically partitioned data[17] which may be mined for scientific or
statistical purposes. Data anonymization techniques are often used to protect
medical data from being re-identified when correlated with publicly available
information. However, it processes the original data and generalizes the
values of attributes which reduces the amount of information[18]. Such
techniques include k-anonymity[19][16], l-diversity[20], t-closeness[21] etc..
are often used by healthcare registries while exchanging HD with external
research institutions. However, our objective is to allow the identification
of HD while ensuring accountability.

Blockchain-based techniques are often used for HD-related transactions [22],
[23], [24], although they bring significant challenges related to validating
the correctness of such solutions [25]. In [24] all transactions are performed
using smart contracts that provide two functions, store and get, and all data
is stored in the blockchain as key-value pairs. In [23] the patients may
delegate hospitals to encrypt their medical records and store them on semi-
trusted cloud servers. However, in our case, the patients are not actively
participating in the process. Rather, the patients remain passive while the
events of their records being accessed get documented which can be viewed by
them later.

Symbol |  Usage
---|---
$p,q,g$ |  Modulus, Subgroup order and generator of the group.
$\pi_{x},y_{x}=g^{\pi_{x}}$ |  Private and Public key of user $A_{x}$
$Y=\bigcup\limits_{x\in X}y_{x}$ |  Set of public keys of all users $X$.
$\xi,\zeta$ |  Symmetric Encryption, Decryption Algorithm.
$H,H_{2}$ |  Cryptographic Hash functions e.g. SHA512
$x\in_{\mathbb{R}}X$ |  $x$ is a random integer from set $X$
$\frac{a}{b}$ |  $ab^{\prime}$ where $b^{\prime}$ is the multiplicative inverse of $b$ in $\mathcal{Z}_{p}$, such that $bb^{\prime}\equiv 1\;(mod\,p)$
$a^{-1}$ |  Multiplicative inverse of $a$ in $\mathcal{Z}_{(p-1)}$, such that $aa^{-1}\equiv 1\;(mod\,(p-1))$
$f(x)\rightarrow y$ |  $y$ is deterministically computable using $f$ and $x$.
$\tau_{x}^{(k)}$ |  $k^{th}$ block in which user $A_{x}$ was active
$\tau_{\widehat{x}}^{(k)}$ |  $k^{th}$ block in which user $A_{x}$ was passive
$\tau^{(r)}$ |  $r^{th}$ block in the ledger, where the information regarding the involvement of any user is either irrelevant or unknown.
TABLE I: Symbol Table

##  III Responsible Record Identification Problem

For privacy-related concerns, the database is often vertically partitioned
where personal information is separated from the sensitive medical
information[16]. In our proposed system, we assume a medical record is de-
identified and the sensitive information is stored separately from the
identifying information. Only the permitted users can identify the patient
associated with that de-identified record and can also find all medical
records associated with the patient. We may refer to this action as _record
identification_. However, there are two constraints applied to the
identification operations. First, even if some adversary gets access to the
storage server, it should not be possible to perform any of these
identification actions without the participation of the permitted users.
Second, in order to ensure the responsibility of the identifier, an entry must
be created in the immutable ledger whenever each of these actions is
performed.

We refer to these actions of record identification as an Access Event. An
Access Event is participated by two users. The permitted user that initiates
the identification process is considered active because this user is actively
communicating in order to identify the record for further analysis. The
patient whose record is being accessed may be unaware of such an event before
it happens. The decision that the records associated with that patient have to
be accessed may not be taken in the active participation of that patient.
Hence we consider the patient as a passive user. We need a ledger that
documents the access events between these two users. Both of these users
should be allowed to browse through the events logged into the ledger
securely. The event participation information must not be disclosed to anyone
other than these active and passive users and the supervisors who have
sufficient credentials to access any random entry and view participation
information. The active user is allowed to navigate to the next and the
previous entries in which the same user was active. Similarly, the passive
user is allowed to navigate to the next and the previous entries in which the
same user was passive. But no users should be allowed to navigate to ledger
entries associated with a different user. We formulate these problems in
Section III-A and III-B (the symbols used in the formulation and throughout
the paper are shown in Table I). Additionally, in order to ensure the
immutability of our ledger, each entry contains the cryptographic hash of its
previous entry, in the order of time, which may not be participated by the
same users.

###  III-A Secure Storage

Figure 1: Secure De-Identification

To secure record identification, we associate each side of the partitioned
record with a ciphertext that we refer to as an anchor. In Figure 1 the
identifying anchor is shown in brown while the sensitive information anchor is
shown in blue. Formally, given a complete record $D_{i}$, the set of personal
information $dp_{i}$ and the set of medical information $dm_{i}$ are annotated
with different anchors $dp_{i}^{*},dm_{i}^{*}$ respectively. However,
$\exists\;\overrightarrow{f}(dp_{i}^{*},x)\rightarrow
dm_{i}^{*},\overleftarrow{f}(dm_{i}^{*},x)\rightarrow dp_{i}^{*}$ can relate
both of these anchors, where $x$ is the secret that can be obtained securely
by the cooperation of permitted users only. For fast retrieval, the records
are indexed with $dp_{i}^{*},dm_{i}^{*}$ .

###  III-B Secure Traversable Ledger

Given two ordered entries in the ledger $\tau_{u}^{(k)},\tau_{u}^{(k+1)}$ in
which user $A_{u}$ is active
$\exists\;\overrightarrow{f_{a}},\overleftarrow{f_{a}}$ such that
$\overrightarrow{f_{a}}(\tau_{u}^{(k)},\pi_{u})\rightarrow\tau_{u}^{(k+1)}$
and $\overleftarrow{f_{a}}(\tau_{u}^{(k+1)},\pi_{u})\rightarrow\tau_{u}^{(k)}$
where $\pi_{u}$ is a secret that only $A_{u}$ has access to. Similarly, if
user $A_{v}$ is passive and $\tau_{v}^{(k)},\tau_{v}^{(k+1)}$ are two ordered
entries in which it was passive, then
$\exists\;\overrightarrow{f_{p}},\overleftarrow{f_{p}}$ such that
$\overrightarrow{f_{p}}(\tau_{v}^{(k)},\pi_{v})\rightarrow\tau_{v}^{(k+1)}$
and
$\overleftarrow{f_{p}}(\tau_{v}^{(k+1)},\pi_{v})\rightarrow\tau_{v}^{(k)}$. In
this paper $\overrightarrow{f_{a}},\overleftarrow{f_{a}}$ are referred to as
active forward and backward functions while
$\overrightarrow{f_{p}},\overleftarrow{f_{p}}$ as passive forward and backward
traversal functions. We also refer to these four functions as _traversal
requirements_ that our proposed solution has to satisfy.

In order to make the traversal secure
$\nexists\overrightarrow{f^{\prime}_{a}}(\tau_{u}^{(k)},x)\rightarrow\tau_{u}^{(k+1)}$
such that $x\neq\pi_{u}$, and same applies for the other traversal functions.
Also there
$\nexists\;F_{a}(\tau_{u}^{(k)},\tau_{u}^{(k+1)})\rightarrow[0,1],F_{p}(\tau_{v}^{(k)},\tau_{v}^{(k+1)})\rightarrow[0,1]$
that deterministically produces a binary output denoting the given two entries
are related to the same active or passive user respectively. In that case, an
adversary can apply that function on all pairs or entries to partition all
entries belonging to the same user.

In this paper, we refer to these entries as _Block_. In Figure 2, we show 4
blocks (shown in yellow rectangles) each referring to an Access Event. In the
first block from the top, user $A_{u^{\prime}}$ is active while the user
$A_{v}$ is passive and it is the first Access Event associated with both of
these users. Similarly, in the fourth block, the user $A_{u}$ is active while
the user $A_{v^{\prime}}$ is passive. The user $A_{u}$ can reach this block
using the function $\overrightarrow{f_{a}}$ and its private credentials, which
is reachable from $\tau_{u}^{(0)}$. Although it is the fourth block in the
order of time, it is the second block that $A_{u}$ can jump into through
active traversal. Similarly, the user $A_{v^{\prime}}$ can jump into this
block by traversing only once from $\tau_{v^{\prime}}^{(0)}$. We label these
blocks from these users’ perspectives. Hence, the same block is referred to as
$\tau_{u}^{(2)}$ and $\tau_{v^{\prime}}^{(1)}$ by users $A_{u}$ and
$A_{v^{\prime}}$. Genesis blocks are shown on the top, which are the first
blocks ($0^{th}$) associated with each user.

Each user is associated with a dedicated chain of events, that has a
traversable total order. However, a block in a user-specific chain may overlap
with some other user’s chain. As these chains are sets of blocks, the ledger
proposed in our work can be described as a union of totally ordered sets. All
these totally ordered sets start with a genesis block that does not have a
mutual order in the context of the user’s secret, which makes this union a
partially ordered set. However, all blocks, including the genesis blocks, are
totally ordered with respect to time. Although the order of these sets is
secret in the absence of users’ secret, the total order of the ledger, which
is the union of all these sets, is transparent as it is ordered by time.
Additionally, ensuring the total order of the blocks inside the ledger implies
that the order of the sets is also maintained. The colored arrows in the
figure denote active or passive traversals. In the end, the creation of a new
block is shown in the figure, which can be traversed from the last blocks
$\tau_{u}^{(2)}$ and $\tau_{v}^{(2)}$.

Figure 2: Traversable Ledger

##  IV Proposed Solution

The human entities in the problem are the Data Managers and Supervisors and
patients. In this paper, we often refer to the Data Managers and Supervisors
as Custodians because they are in the jurisdiction of the Institution. A
Custodian is permitted to access and identify the medical record(s) without
depending on any other custodian. The responsibility is enforced by creation
of an entry in the immutable ledger. The Database is vertically partitioned
but not encrypted. Hence any unauthorized user, if got access to the Database
may see the medical records but will not have the ability to identify the
patient associated with the medical record. We choose to keep the data
unencrypted to permit fast access and query processing which is often required
for medical research. The focus of this work is to make the Custodians
responsible for record identification. So, we do not consider the data thefts
as long as the stolen data still remains non-identifiable. With this setup, an
adversary with database access may still use statistical techniques to re-
identify the vertically partitioned data. However, our paper does not deal
with re-identification threats. The focus of our paper is concentrated on
enforcing the accountability of identification.

###  IV-A System Design

The proposed solution consists of Custodians, Patients, a Trusted Server, a
Database, and a Key-value store that serves the purpose of the ledger. Only
the Trusted Server (TS) has access to the database stored on a different
Server. The events are logged in the key-value store accessible by the TS and
all other human entities. A Custodian performs operations like _Insertion_ ,
_Identification_ , etc. on the de-identified HD through the TS. After each
operation, an entry is written into the Ledger. The ledger consists of entries
referred to as blocks, each associated with an Access Event. Each block
contains the cryptographic hash of its previous block in the ledger. With
appropriate credentials, the users can selectively browse through the blocks
that are associated with them. The TS is the only entity that writes into the
ledger. Anyone including the custodians and the patients can read from the
ledger. We follow a semi-honest adversarial model for the TS, which implies
that the TS follows the protocol when interacting with the custodians.
However, the TS can be curious, to explore the database with an intention to
identify some medical records while not interacting with any custodians. Our
scheme requires the cooperation of two entities in order to identify a record,
one of which is the TS and the other is a custodian. Both custodians and
patients can traverse the ledger and read the blocks related to them. We
consider the custodians and patients to be malicious. They may deviate from
the protocol to gain information about other custodians or patients.

We use Diffie Hellman[26] based construction for the anchors and the _blocks_.
Hence, security is based on the assumption that the adversary cannot solve CDH
and DDH problems defined in Definition IV.1 and IV.2. Each actor (Custodians
and TS) $A_{t}$ in our system has a pair of private key $t$ and public key
$g^{t}$ generated by the TS, such that $\exists t^{-1}:g^{tt^{-1}}\equiv
g\,(modp)$. We assume that the key generation and distribution process is
secure. In this paper the symbols $A_{u},A_{v},A_{w}$ are used for denoting an
Active user (Data Managers and Supervisors), Passive user (Patients) and the
TS, respectively. We use the symbol $A_{s}$ to specifically denote a
supervisor.

######  Definition IV.1.

Given a cyclic group $G$ of order $q$, with generator $g$, and
$\\{g^{a},g^{b}\\}$ Computational Diffie Hellman (CDH) problem is to compute
$g^{ab}$ where $a,b\in_{R}Z_{q}^{*}$.

######  Definition IV.2.

Given a cyclic group $G$ of order $q$, with generator $g$, and
$\\{g^{a},g^{b}\\}$ Decisional Diffie Hellman (DDH) problem is to distinguish
$g^{ab}$ from $g^{c}$ where $a,b,c\in_{R}Z_{q}^{*}$.

###  IV-B Securely Identifiable Vertical Partitioning

In Figure 3, the formulation of a vertically partitioned record is shown.

The medical information parts of these records $\\{M_{v,1},M_{v,2},\dots\\}$
do not include any identifying information. The Identifying information (on
the left) and the De-Identified information (on the right) are stored in
different tables. The identifying information part contain a random number
$p_{v}\in_{R}[1,2^{512}]$ indexed by the public key $g^{\pi_{v}}$ of the
patient. Each medical record $M_{v,j}$ is associated with an anchor $a_{v,j}$
expressed as a tuple $\\{m_{v,j},\eta_{v,j},t_{v,j}\\}$ indexed by $m_{v,j}$.
The construction of anchor $a_{v,j}$ is shown in Equation 1.

The system is initialized with $\theta\in_{\mathbb{R}}\mathbb{Z}_{p}$ such
that $\nexists\;\theta^{-1}\in\mathbb{Z}_{p}$, but for its hash
$h=H(g^{\theta})$, $\exists h^{-1}$ such that $g^{hh^{-1}}\;\equiv
g\,(mod\;p)$.

Figure 3: Database Anchors

$\begin{split}m_{v,j}&=\xi\Big{(}g^{\pi_{v}},H_{2}(g^{\theta
t_{v,j-1}})\Big{)}\\\ \eta_{v,j}&=t_{v,j-1}H(g^{\theta t_{v,j}})\end{split}$
(1)

With knowledge of $t_{v,j}$ and $g^{\theta}$, one can compute $H_{2}(g^{\theta
t_{v,j}})$ which is used as the key in the symmetric encryption algorithm
$\xi$. Hence, with that knowledge, it is also possible to decrypt $m_{v,j+1}$
and extract $g^{\pi_{v}}$ and identify the patient. $t_{v,j}$ a random number
stored as a plaintext in $a_{v,j}$. Similarly, one can also extract $t_{v,j}$
from $\eta_{v,j+1}$ by computing the hash of $(g^{\theta})^{t_{v,j+1}}$.
However, to iterate through all medical records of a patient, we need a first
record to start with. However, the first record needs a $t_{v,-1}$ which does
not exist. Hence, we use $p_{v}$ associated with the identifying part of the
record. Therefore, we can relate any patient and sensitive information of that
patient as long as $g^{\theta}$ is known.

However, $\theta$ or $g^{\theta}$ is not remembered or stored in any
persistent storage. Rather, an access key is computed using that and the
user’s private key

as $(g^{\pi_{t}})^{\theta w}=g^{\pi_{t}\theta w}$

A user $A_{u}$ can use the multiplicative inverse of its private key $\pi_{u}$
and send that to the Trusted server who can use the multiplicative inverse of
$w$ to recover the $g^{\theta}$ which was previously lost in the beginning as
shown in Equations 2.

$\begin{split}(g^{\pi_{u}\theta w})^{\pi_{u}^{-1}}=g^{\theta
w}\Rightarrow(g^{\theta w})^{w^{-1}}=g^{\theta}\end{split}$ (2)

However, we need to make the exchange in a way that enforces the creation of
an entry in the immutable ledger. So, the exchange of shared secrets is
incorporated into a protocol. We call that process Request for Sensitive
Information (RSI). The RSI contains the type of operation the active user
intends to perform (e.g. identify, insert, fetch etc..) and the related data.
The other is when the custodians want to identify the patients associated with
a set of medical records. In the next Section, we formulate the entries in the
immutable ledger. In Section IV-F we explain the construction of the entries,
and then we describe the protocol that integrates ledger construction and
exchange of access key.

###  IV-C Ledger Formulation

d Traversability Requirements respectively. The ledger entries, referred to as
blocks, are constructed as an effect of the Access Event, which happens in
collaboration with the TS which is supposed to enforce the creation of the
block. Hence, the TS constructs the block and posts it on the ledger. However,
the blocks have to be constructed in a way that satisfies the _traversal
requirements_ described in Section III. Every block has four parts, _Address_
, _Active_ , _Passive_ , and _Content_ as shown in Figure 4. The formulations
of the first three parts are presented in Equation 3, 4 and 5. Each block is
formulated using two random numbers $r_{u}^{(k)},r_{v}^{(k)}$ that are
cryptographically associated with the active and the passive parts of the
block. The _Address_ component $\\{c_{u}^{(k)},c_{\widehat{v}}^{(k)}\\}$ is
used to _index_ each block for fast retrieval. The Active and Passive parts
contain information for the Active and Passive Traversals in a forward
$\\{\overrightarrow{l_{u}^{(k)}},\overrightarrow{l_{\widehat{v}}^{(k)}}\\}$
and backward
$\\{\overleftarrow{l_{u}^{(k)}},\overleftarrow{l_{\widehat{v}}^{(k)}}\\}$
direction. In the next section, we discuss how the _traversal requirements_
are satisfied by this formulation.

Figure 4: Block Formulation

$c_{u}^{(k)}=\tau_{u}^{(k-1)}H\Big{(}g^{\pi_{u}r_{u}^{(k-1)}}\Big{)}$ (3a) |  $c_{\widehat{v}}^{(k)}=\tau_{\widehat{v}}^{(k-1)}H\Big{(}g^{\pi_{v}r_{v}^{(k-1)}}\Big{)}$ (3b)
---|---

$\displaystyle\begin{split}\overrightarrow{l_{u}^{(k)}}=&g^{r_{u}^{(k)}}\end{split}$
(4a)
$\displaystyle\begin{split}\overleftarrow{l_{u}^{(k)}}=&H(g^{\pi_{u}r_{v}^{(k)}})g^{r_{u}^{(k-1)}}\end{split}$
(4b)
$\displaystyle\begin{split}l_{u}^{(k)*}=&H\Big{(}g^{w\pi_{u}r_{u}^{(k)}}g^{\pi_{u}}\Big{)}\end{split}$
(4c)

$\displaystyle\begin{split}\overrightarrow{l_{\widehat{v}}^{(k)}}=&g^{r_{v}^{(k)}}\end{split}$
(5a)
$\displaystyle\begin{split}\overleftarrow{l_{\widehat{v}}^{(k)}}=&H(g^{\pi_{v}r_{u}^{(k)}})g^{r_{v}^{(k-1)}}\end{split}$
(5b)
$\displaystyle\begin{split}l_{vw}^{(k)}=&H(g^{wr_{v}^{(k)}})g^{h\pi_{v}r_{v}^{(k)}}\end{split}$
(5c)

###  IV-D Traversal

The objective of the _active forward traversal_ function
$\overrightarrow{f_{a}}(\tau_{u}^{(k-1)},\pi_{u})$ is to make it possible to
compute $c_{u}$ using private key of $A_{u}$, as shown in Equation 6a. This
$c_{u}$ is then looked up in the index to find the block id $\tau_{u}^{(k)}$
and then read the block. However, for the _active backward traversal_ , the
function $\overleftarrow{f_{a}}(\tau_{u}^{(k)},\pi_{u})$ computes the id of
the previous active block without requiring looking up in the index of the
addresses. The traversal function
$\overleftarrow{f_{a}}(\tau_{u}^{(k)},\pi_{u})$ is modeled as shown in
Equation 6b.

The _passive forward traversal_ and _passive backward traversal_ are very
similar to the active one, however instead of using $\pi_{u}$, it requires
$\pi_{v}$ which is the private key of the passive user $A_{v}$. The traversal
functions $\overrightarrow{f_{p}}$ and $\overleftarrow{f_{p}}$ are shown in
Equation 7a and 7b respectively.

$\displaystyle\begin{split}\overrightarrow{f_{a}}(\tau_{u}^{(k-1)},\pi_{u})&=\tau_{u}^{(k-1)}H\Bigg{(}\Big{(}\overrightarrow{l_{u}^{(k-1)}}\Big{)}^{\pi_{u}}\Bigg{)}=c_{u}^{(k)}\end{split}$
(6a)
$\displaystyle\begin{split}\overleftarrow{f_{a}}(\tau_{u}^{(k)},\pi_{u})&=\frac{c_{u}}{H\Bigg{(}\Bigg{(}\frac{\overleftarrow{l_{u}^{(k)}}}{H\Big{(}\Big{(}\overrightarrow{l_{v}^{(k)}}\Big{)}^{\pi_{u}}\Big{)}}\Bigg{)}^{\pi_{u}}\Bigg{)}}=\tau_{u}^{(k-1)}\end{split}$
(6b)
$\displaystyle\begin{split}\overrightarrow{f_{p}}(\tau_{\widehat{v}}^{(k-1)},\pi_{v})&=\tau_{\widehat{v}}^{(k-1)}H\Bigg{(}\Big{(}\overrightarrow{l_{\widehat{v}}^{(k-1)}}\Big{)}^{\pi_{v}}\Bigg{)}=c_{\widehat{v}}^{(k)}\end{split}$
(7a)
$\displaystyle\begin{split}\overleftarrow{f_{p}}(\tau_{\widehat{v}}^{(k)},\pi_{v})&=\frac{c_{\widehat{v}}}{H\Bigg{(}\Bigg{(}\frac{\overleftarrow{l_{\widehat{v}}^{(k)}}}{H\Big{(}\Big{(}\overrightarrow{l_{u}^{(k)}}\Big{)}^{\pi_{v}}\Big{)}}\Bigg{)}^{\pi_{v}}\Bigg{)}}=\tau_{\widehat{v}}^{(k-1)}\end{split}$
(7b)

###  IV-E Genesis Block

As the genesis block is the first block belonging to the user. It is not meant
to traverse backward from that block. Hence, only the forward traversal
information is sufficient, and we don’t include the
$\overleftarrow{l_{u}^{(0)}}$ and $\overleftarrow{l_{\widehat{v}}^{(0)}}$ as
we have done in other blocks. Also, as the genesis block does not describe any
actual access event it does not follow the usual semantics of active and
passive users. Rather the same user is simultaneously considered active and
passive. The Equations 8 and 9 describe the formulation of the active and the
passive parts of the genesis block.

$\displaystyle\begin{split}\overrightarrow{l_{u}^{(0)}}=&g^{r_{t}^{(0)}}\end{split}$
(8a)
$\displaystyle\begin{split}l_{u}^{(0)*}=&H\Big{(}g^{w\pi_{t}r_{t}^{(0)}}g^{\pi_{t}}\Big{)}\end{split}$
(8b)

$\displaystyle\begin{split}\overrightarrow{l_{\widehat{u}}^{(0)}}=&g^{r_{t}^{(0)}}\end{split}$
(9a)
$\displaystyle\begin{split}l_{uw}^{(0)}=&H(g^{wr_{t}^{(0)}})g^{h\pi_{t}r_{t}^{(0)}}\end{split}$
(9b)

Genesis blocks do not have addresses. The id of the block is computed as a
hash of the public key of the user.

###  IV-F Construction

Blocks are constructed by the TS through active participation with the Active
user $A_{u}$. The Request for Sensitive Information (RSI) contains information
regarding the requested operation. The TS constructs the block registering the
event and returns the information requested. While retrieving that information
the TS gets to know about the patient who is the passive user $A_{v}$ in this
context. With the knowledge of $A_{u}$, $A_{v}$, and some private information
computed by the $A_{u}$ the TS constructs the block.

We propose a two-stage protocol (shown in Figure 5) through which the TS
obtains sufficient information securely without damaging the privacy of
$A_{u}$. In the first stage of the protocol, the active user claims to be
$A_{u}$ by sending the public key $g^{\pi_{u}}$ and the last block
$\tau_{u}^{(n)}$ in which $A_{u}$ was active. It also sends a token $\Gamma$
calculated as $\Big{(}\overrightarrow{l_{u}^{(n)}}\Big{)}^{\pi_{u}}$ using
which the TS verifies that claim of identity. TS computes $H(y\Gamma^{w})$ and
compares that with $l_{u}^{(n)*}$. If they are the same, then the block
$\tau_{u}^{(n)}$ is a block in which $A_{u}$ participated as an active user
and the claim of identity is also correct because it has access to the private
key of $A_{u}$. To verify whether $\tau_{u}^{(n)}$ is the last such block TS
computes $\tau_{u}^{(n)}\Gamma=c_{u}^{(n+1)}$ and checks whether it already
exists in the index of addresses. If the computed $c_{u}^{(n+1)}$ is not found
and the claim of identity is proven, then the user is not malicious and the
protocol follows the next stage. Otherwise, TS rejects the request.

Figure 5: Protocol for Communicating RSI

In the second stage of the protocol, the active user communicates the intended
operation and related data along with the access key, using which the TS
recomputes $g^{\theta}$, which was lost initially. The TS generates a random
$\lambda\in Z_{q}^{*}$, computes its inverse $\lambda^{-1}$ and sends
$\lambda\big{(}g^{\pi_{u}}\big{)}^{w}=\lambda g^{w\pi_{u}}$ to the $A_{u}$.
$A_{u}$ can extract the $\lambda$ by computing $\big{(}g^{w}\big{)}^{\pi_{u}}$
and then sends $g^{\theta\lambda w}$ calculated using inverse of its private
key $(g^{\theta\pi_{u}w})^{\lambda\pi_{u}^{-1}}$.

The tuple in the third message shown in Figure 5 summarizes the message that
the Active user sends to the TS in stage 2. The $\epsilon$ and $D_{\epsilon}$
denote the action that the active user intends to perform and the
corresponding data respectively. The set of possible actions and their
corresponding data are represented in Table II.

$\epsilon$ | $D_{\epsilon}$ |  Intention
---|---|---
identify | $a_{v,j}$ |  Retrieve public key of the patient associated with medical information $a_{v_{j}}$
fetch | $g^{\pi_{v}}$ |  Fetch all records of patient identified by public key
insert | $g^{\pi}_{v},A$ |  Insert records $A=\\{a_{v,1}\dots a_{v,m}\\}$ and associate them with patient identified by $g^{\pi_{v}}$
delete | $a_{v,j}$ |  Delete Record $a_{v,j}$
TABLE II: Actions in Access Event

After receiving the response, the TS uses the $\lambda^{-1}$ and $w^{-1}$ to
reconstruct $g^{\theta}$. This $g^{\theta}$ is the secret using which the
database anchors are encrypted. TS can get the public key of the passive user
$g^{\pi_{v}}$ either from $D_{w}$ or from the database using $g^{\theta}$. So,
at this stage of the protocol, TS is aware of the passive user too.

Now the TS has enough information to construct the next block
$\tau_{u}^{(n+1)}$ which is also $\tau_{v}^{(n+1)}$ for the passive user
$A_{v}$. TS generates two random numbers, $r_{u}^{(n+1)}$ and $r_{v}^{(n+1)}$,
such that there exist not multiplicative inverse in $\mathbb{Z}_{p-1}$ and the
inequality in Equation 10 is satisfied.

$H_{2}\Big{(}g^{\pi_{v}r_{u}^{(n+1)}}\Big{)}\not\equiv
H_{2}\Big{(}g^{\pi_{u}r_{u}^{(n)}}\Big{)}\;(mod\;2)$ (10)

The construction of the parts of block $\tau_{u}^{(n+1)}$ are summarized in
Equations 11, 12 and 13.

$\displaystyle\begin{split}\overrightarrow{l_{u}^{(n+1)}}&\coloneqq
g^{r_{u}^{(n+1)}}\end{split}$ (11a)
$\displaystyle\begin{split}\overleftarrow{l_{u}^{(n+1)}}&\coloneqq
H\Big{(}y_{u}^{r_{v}^{(n+1)}}\Big{)}\overrightarrow{l_{u}^{(n)}}=H\Big{(}g^{\pi_{u}r_{v}^{(n+1)}}\Big{)}g^{r_{u}^{(n)}}\end{split}$
(11b) $\displaystyle\begin{split}l_{u}^{(n+1)*}&\coloneqq
H\Big{(}y_{u}^{wr_{u}^{(n+1)}}y_{u}\Big{)}=H\Big{(}g^{\pi_{u}wr_{u}^{(n+1)}}g^{\pi_{u}}\Big{)}\end{split}$
(11c)
$\displaystyle\begin{split}\overrightarrow{l_{\widehat{v}}^{(n+1)}}&\coloneqq
g^{r_{\widehat{v}}^{(n+1)}}\end{split}$ (12a)
$\displaystyle\begin{split}\overleftarrow{l_{\widehat{v}}^{(n+1)}}&\coloneqq
H\Big{(}y_{\widehat{v}}^{r_{u}^{(n+1)}}\Big{)}\overrightarrow{l_{\widehat{v}}^{(n)}}=H\Big{(}g^{\pi_{v}r_{u}^{(n+1)}}\Big{)}g^{r_{v}^{(n)}}\end{split}$
(12b) $\displaystyle\begin{split}l_{vw}^{(n+1)}&\coloneqq
H\Big{(}y_{w}^{r_{v}^{(n+1)}}\Big{)}y_{v}^{hr_{v}^{(n+1)}}=H\Big{(}g^{wr_{v}^{(n+1)}}\Big{)}g^{\pi_{v}hr_{v}^{(n+1)}}\end{split}$
(12c)
$\displaystyle\begin{split}c_{u}^{(n+1)}&\coloneqq\tau_{u}^{(n)}\Gamma\end{split}$
(13a)
$\displaystyle\begin{split}c_{\widehat{v}}^{(n+1)}&\coloneqq\tau_{\widehat{v}}^{(n)}\Bigg{(}\frac{l_{vw}^{(n)}}{H\Big{(}\Big{(}\overrightarrow{l_{\widehat{v}}^{(n)}}\Big{)}^{w}\Big{)}}\Bigg{)}^{h^{-1}}=\tau_{\widehat{v}}^{(n)}\Big{(}g^{\pi_{v}r_{v}^{(k)}}\Big{)}\end{split}$
(13b)

###  IV-G Encrypting Block Contents

The block contents should be encrypted in such a way that they can be
decrypted by only the $A_{u}$, $A_{v}$ involved in that block, and all
supervisors. We want that decryption also to happen offline so that it does
not require any network communication. The TS formulates a straight line
primarily with two coordinates (shown in Equation 14) that only the users
$A_{u}$ and $A_{v}$ can compute. Although the TS can compute those coordinates
while construction, it loses the information it needs to reconstruct that
again. Once the straight line is constructed, it finds two random coordinates
that satisfy that linear equation. One of those coordinates is published with
that block as plain text along with the $x$ value of the other. The
cryptographic hash of the $y$ value of the other random coordinate is used as
a password to symmetrically encrypt the message.

$\displaystyle
d^{(u)}=\begin{bmatrix}H_{2}\Big{(}g^{\pi_{u}r_{u}^{(n)}}\Big{)}\\\
c_{v}\end{bmatrix},$ $\displaystyle\quad\quad
d^{(v)}=\begin{bmatrix}H_{2}\Big{(}g^{\pi_{v}r_{u}^{(n+1)}}\Big{)}\\\
c_{u}\end{bmatrix}$ (14)

We generate two random coordinates $\gamma,\delta$ on that line and publish
$\gamma$ and $\delta_{x}$ with the block. The contents are encrypted using
$H_{2}(\delta_{y})$. Both active and passive users can compute either
$d^{(u)}$ or $d^{(v)}$ and then interpolate a straight line using $\gamma$
which is available as a plaintext. Then, the users put $x=\delta_{x}$ on that
equation and calculate $y=\delta_{y}$. Once $\delta_{y}$ is retrieved, its
hash $H_{2}(\delta_{y})$ can be computed, using which the encrypted message
can be decrypted and the plaintext can be obtained.

However, the supervisors cannot compute either $d^{(u)}$ or $d^{(v)}$, hence
cannot use $\lambda$ to interpolate the straight line. As the supervisors can
also perform access events they too have their access key like the Data
Managers. Additionally, they have $g^{\phi w\pi_{s}}$ which is specifically
used for viewing, but unlike $g^{\theta}$ it is not lost by the TS. Although
$g^{\theta}$ is lost, it is reconstructed in the second stage of the protocol
by the TS. Hence, the TS computes a suffix $\Big{(}g^{\theta w}g^{\phi
w}\Big{)}^{\gamma_{x}}$ and multiplies the $H_{2}(\delta_{y})$ as shown in
Equation 15 and stores that $\delta_{y}^{(s)}$ in the block.

$\delta_{y}^{(s)}=H_{2}(\delta_{y})\Big{(}g^{\theta w}g^{\phi
w}\Big{)}^{\gamma_{x}}=H_{2}(\delta_{y})g^{(\theta+\phi)w\gamma_{x}}$ (15)

The supervisors $A_{s}$ can compute the suffix and obtain $H_{2}(\delta_{y})$
by division in $\mathcal{Z}_{p}$ as shown in Equation 16.

$\frac{\delta_{y}^{(s)}}{\Big{(}(g^{\phi w\pi_{s}})^{\pi_{s}^{-1}}(g^{\theta
w\pi_{s}})^{\pi_{s}^{-1}}\Big{)}^{\gamma_{x}}}$ (16)

However, the $A_{u}$ and $A_{v}$ also can compute $H_{2}(\delta_{y})$ and can
extract the suffix $g^{(\theta+\phi)w\gamma_{x}}$ through division. As
$\gamma_{x}$ is known anyone can compute $\gamma_{x}^{-1}$ and and extract
$g^{(\theta+\phi)w}=(g^{(\theta+\phi)w\gamma_{x}})^{\gamma_{x}^{-1}}$ using
that. Once extracted it can be reused with some other $\gamma_{x}$ associated
with some other block. Hence, while generating random $\gamma$ we need to
ensure that $\nexists\gamma_{x}^{-1}$ such that
$\gamma_{x}\gamma_{x}^{-1}\equiv 1\in\mathcal{Z}_{(p-1)}$. Finally a checksum
of the block is calculated and the blocks are signed by the Trusted Server.

##  V Evaluation

We perform three experiments to measure the performance of our proposed
solution in terms of CPU time consumption.

#### Experimental Setup:

To test the performance of our proposed scheme we have implemented our
cryptographic functions in C++ using Crypto++ library. The Trusted Server has
been implemented as a TCP Server using the ‘Boost Asio‘ library. The program
that takes the private key of the user and performs operations described in
Table II is implemented as a TCP client. PostgreSQL database has been used for
storing HD. Redis key-value store has been used as an event log and for the
index. To measure the performance of active or passive traversal we implement
a reader application that takes the private key of a user and performs
traversal by accessing the key-value store.

We initialize the system with 5 managers, 4 supervisors, 7 patients and their
genesis records in the database. In this paper, we do not focus on secure
distribution of the private keys to the users. Hence, we assume that the
private keys are securely delivered to them.

#### Experiment 1

First, we measure the CPU time consumed by the TS during the insertion
operation by sending a series of bulk insertion requests for 5 patients. In
each insertion operation, a batch of records is sent. We vary the batch size
from 10 to 50 records per request in each iteration. So, at the end of
$20^{th}$ request, there are 200 records associated with patient 1 and 50*20
=1000 associated with the $5^{th}$ patient. The results are shown in Figure 6.
We observe that the time consumed for inserting records is not related to the
total number of HD in the database. However, it is directly proportional to
the number of existing records already associated with a patient. Such a
result is expected because the TS performs a linear traversal over the
database while inserting a record. It is observed that the time consumption is
more than 300ms when there are 1000 records associated with a single patient.

$5$$10$$15$$20$$0ms$$100ms$$200ms$$300ms$Number of transactions
$\blacktriangleright$CPU Time $\blacktriangleright$1020304050 Figure 6: Bulk
Insertion
$200$$400$$600$$800$$1{,}000$$50ms$$100ms$$150ms$$200ms$$250ms$$300ms$Number
of Records $\blacktriangleright$CPU Time $\blacktriangleright$ Figure 7: Fetch
All Entries $50$$100$$150$$200$$250$$100ms$$200ms$$300ms$$400ms$$500ms$Number
of Entries $\blacktriangleright$CPU Time $\blacktriangleright$Active
ForwardActive BackwardPassive ForwardPassive Backward Figure 8: Traversal

#### Experiment 2

Next, we fetch all records associated with a single patient and measure the
CPU time consumed. The results shown in Figure 7 suggest that the time
consumed for retrieving HD is directly proportional to the number of records
associated with a patient.

#### Experiment 3

In this experiment, we check the performance of ledger traversal.

We perform several traversal requests to the ledger each limiting the number
of entries from 50 to 250. The results are shown in Figure 8. We observe both
active and passive forward traversal have the same performance
characteristics. Although the Passive traversal is slightly more expensive
than the Forward ones, the Active Backward traversal is more expensive than
the Passive one.

##  VI Conclusion and Discussion

In this paper, we have proposed a secure, responsible, privacy-preserving
document storage and retrieval technique. The solution can be used for
different business processes other than healthcare. Even in healthcare, the
applications of such systems are not limited to health registries. However, a
generalized use case may involve more than two users in one event.

Furthermore, although the cost of the insertion operation does not depend on
the number of total records in the database, it depends on the number of
records associated with one patient. Therefore, it is suitable for scenarios
where the per-patient record is lower than the total number of records. Also,
the traversability of the blocks in the ledger cannot be verified by any
entity because that entity can also partition the ledger into blocks
associated with one particular user or the other. Not only that, but also the
verifier will be able to understand the sequence of events associated with any
user inside the system. This leads to another important problem that future
work may address. In our proposed solution, the immutability of the ledger is
maintained by annotating an entry with the hash of the previous entry.
However, it is a centralized system implemented using a key-value store. An
implementation using blockchain-based distributed ledger platforms may provide
byzantine fault tolerance against manipulation of the ledger.

## Acknowledgment

This work is supported by the Research Council of Norway, grant number 288106.
We also acknowledge Jan F. Nygård from the Cancer Registry of Norway (CRN) for
discussing the internal operations of CRN regarding this problem.

## References

  * [1] S. Chatterjee, A. Chattopadhyay, S. N. Senapati, D. R. Samanta, L. Elliott, D. Loomis, L. Mery, and P. Panigrahi, “Cancer registration in India - Current scenario and future perspectives,” _Asian Pacific Journal of Cancer Prevention_ , vol. 17, no. 8, 2016.
  * [2] K. Laugesen, J. F. Ludvigsson, M. Schmidt, M. Gissler, U. A. Valdimarsdottir, A. Lunde, and H. T. Sørensen, “Nordic health registry-based research: A review of health care systems and key registries,” _Clinical Epidemiology_ , vol. 13, no. April, 2021.
  * [3] C. Bouchardy, E. Rapiti, and S. Benhamou, “Cancer registries can provide evidence-based data to improve quality of care and prevent cancer deaths,” _Ecancermedicalscience_ , vol. 8, no. 1, 2014.
  * [4] E. Pukkala, G. Engholm, L. K. Højsgaard Schmidt, H. Storm, S. Khan, M. Lambe, D. Pettersson, E. Ólafsdóttir, L. Tryggvadóttir, T. Hakanen, N. Malila, A. Virtanen, T. B. Johannesen, S. Larønningen, and G. Ursin, “Nordic Cancer Registries - an overview of their procedures and data comparability,” _Acta Oncologica_ , vol. 57, no. 4, 2018.
  * [5] K. Chaudhry and U. K. Luthra, “Cancer Registration in India,” _Cancer_ , 2002. [Online]. Available: https://main.mohfw.gov.in/sites/default/files/Cancer Registration In India.pdf
  * [6] S. Bose and D. Marijan, “A survey on privacy of health data lifecycle: A taxonomy, review, and future directions,” 2023.
  * [7] Q. Xia, E. B. Sifah, J. G. Kwame Omono Asamoah, X. Du, and M. Guizani, “MeDShare : Trust-less Medical Data Sharing Among,” _IEEE Access_ , vol. 5, 2017.
  * [8] R. Gajanayake, R. Iannella, and T. Sahama, “Privacy oriented access control for electronic health records,” _Electronic Journal of Health Informatics_ , vol. 8, no. 2, 2014.
  * [9] P. Thummavet and S. Vasupongayya, “A novel personal health record system for handling emergency situations,” _2013 International Computer Science and Engineering Conference, ICSEC 2013_ , 2013.
  * [10] J. T. Jose and S. Anju, “Threshold Cryptography Based Secure Access Control for Electronic Medical Record in an Intensive Care Unit,” vol. 2, no. 9, 2013\.
  * [11] S. Eskeland and V. A. Oleshchuk, “EPR access authorization of medical teams based on patient consent,” vol. P-118, 2007.
  * [12] M. Yuliana, H. A. Darwito, A. Sudarsono, and G. Yofie, “Privacy and security of sharing referral medical record for health care system,” _Proceeding - 2016 2nd International Conference on Science in Information Technology, ICSITech 2016: Information Science for Green Society and Environment_ , 2017.
  * [13] A. Sudarsono, M. Yuliana, and H. A. Darwito, “A secure data sharing using identity-based encryption scheme for e-healthcare system,” _Proceeding \- 2017 3rd International Conference on Science in Information Technology: Theory and Application of IT for Education, Industry and Society in Big Data Era, ICSITech 2017_ , vol. 2018-Janua, 2017.
  * [14] J. Liu, X. Li, L. Ye, H. Zhang, X. Du, and M. Guizani, “BPDS: A Blockchain Based Privacy-Preserving Data Sharing for Electronic Medical Records,” _2018 IEEE Global Communications Conference, GLOBECOM 2018 - Proceedings_ , 2018.
  * [15] C. Ge, C. Yin, Z. Liu, L. Fang, J. Zhu, and H. Ling, “A privacy preserve big data analysis system for wearable wireless sensor network,” _Computers and Security_ , vol. 96, 2020.
  * [16] J. J. Yang, J. Q. Li, and Y. Niu, “A hybrid solution for privacy preserving medical data sharing in the cloud environment,” _Future Generation Computer Systems_ , vol. 43-44, 2015.
  * [17] N. Domadiya and U. P. Rao, “Improving healthcare services using source anonymous scheme with privacy preserving distributed healthcare data collection and mining scheme with privacy preserving distributed healthcare data,” _Computing_ , no. August, 2021.
  * [18] S. R. Oh, Y. D. Seo, E. Lee, and Y. G. Kim, “A comprehensive survey on security and privacy for electronic health data,” _International Journal of Environmental Research and Public Health_ , vol. 18, no. 18, 2021.
  * [19] H. Li, F. Guo, W. Zhang, J. Wang, and J. Xing, “(a,k)-Anonymous Scheme for Privacy-Preserving Data Collection in IoT-based Healthcare Services Systems,” _Journal of Medical Systems_ , vol. 42, no. 3, 2018.
  * [20] A. Machanavajjhala, J. Gehrke, D. Kifer, and M. Venkitasubramaniam, “L-diversity: privacy beyond k-anonymity,” in _22nd International Conference on Data Engineering (ICDE’06)_. IEEE, 2006.
  * [21] N. Li, “t -Closeness : Privacy Beyond k -Anonymity and -Diversity,” no. 2, 2011\.
  * [22] M. S. Arbabi, C. Lal, N. R. Veeraragavan, D. Marijan, J. F. Nygård, and R. Vitenberg, “A survey on blockchain for healthcare: Challenges, benefits, and future directions,” _IEEE Communications Surveys and Tutorials_ , vol. 25, no. 1, pp. 386–424, 2023.
  * [23] H. Huang, P. Zhu, F. Xiao, X. Sun, and Q. Huang, “A blockchain-based scheme for privacy-preserving and secure sharing of medical data,” _Computers and Security_ , vol. 99, 2020.
  * [24] H. Tian, J. He, and Y. Ding, “Medical Data Management on Blockchain with Privacy,” _Journal of Medical Systems_ , vol. 43, no. 2, 2019.
  * [25] D. Marijan and C. Lal, “Blockchain verification and validation: Techniques, challenges, and research directions,” _Computer Science Review_ , vol. 45, p. 100492, 2022. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S1574013722000314
  * [26] W. Diffie and M. Hellman, “New directions in cryptography,” 1976.


2120191124882

# Alternating Hamiltonian cycles in $2$-edge-colored multigraphs††thanks: This
research was supported by grants UNAM-DGAPA-PAPIIT IN104717 and CONACyT
CB-2013/219840. The first and third authors were supported by postdoctoral
positions under the grant CONACyT CB-2013/219840 at Instituto de Matemáticas
at the Universidad Nacional Autónoma de México.

Alejandro Contreras-Balbuena1,3 Corresponding author. Hortensia Galeana-
Sánchez1  Ilan A. Goldfeder1,2  Instituto de Matemáticas, Universidad Nacional
Autónoma de México, México
Departamento de Matemáticas, Universidad Autónoma Metropolitana, Iztapalapa,
México
Universidad del Istmo, Campus Tehuantepec, México

(2018-10-11; 2019-04-27, 2019-05-18; 2019-05-28)

###### Abstract

A path (cycle) in a $2$-edge-colored multigraph is alternating if no two
consecutive edges have the same color. The problem of determining the
existence of alternating Hamiltonian paths and cycles in $2$-edge-colored
multigraphs is an $NP$-complete problem and it has been studied by several
authors. In Bang-Jensen and Gutin’s book Digraphs: Theory, Algorithms and
Applications, it is devoted one chapter to survey the latest results on this
topic. Most results on the existence of alternating Hamiltonian paths and
cycles concern on complete and bipartite complete multigraphs and a few ones
on multigraphs with high monochromatic degrees or regular monochromatic
subgraphs. In this work, we use a different approach imposing local conditions
on the multigraphs and it is worthwhile to notice that the class of
multigraphs we deal with is much larger than, and includes, complete
multigraphs, and we provide a full characterization of this class.

Given a $2$-edge-colored multigraph $G$, we say that $G$ is _$2$
-$\mathcal{M}$-closed_ (resp. _$2$ -$\mathcal{NM}$-closed)_ if for every
monochromatic (resp. non-monochromatic) $2$-path $P=(x_{1}$, $x_{2}$,
$x_{3})$, there exists an edge between $x_{1}$ and $x_{3}$. In this work we
provide the following characterization:

> A $2$-$\mathcal{M}$-closed multigraph has an alternating Hamiltonian cycle
> if and only if it is color-connected and it has an alternating cycle factor.

Furthermore, we construct an infinite family of $2$-$\mathcal{NM}$-closed
graphs, color-connected, with an alternating cycle factor, and with no
alternating Hamiltonian cycle.

###### keywords:

edge-colored multigraphs, Hamiltonian cycles, alternating Hamiltonian cycles

A trail $T$ in a $2$-edge-colored multigraph is _alternating_ if no two
consecutive edges of $T$ have the same color. A great number of problems have
been modelled by using edge-colored multigraphs. Bang-Jensen and Gutin (1997)
suggested that Petersen (1891)’s paper seems to be the first place where one
can find applications of alternating colored trails. Moreover, there are
applications of alternating colored trails in genetics, Alizadeh et al.
(1995); Dorninger (1987, 1994); Dorninger and Timischl (1987); Pevzner (1995),
transportation and connectivity problems, Gourvès et al. (2010); Wirth and
Steffan (2001), social sciences, Chou et al. (1994), and graphs models for
conflicts resolutions, Xu et al. (2010, 2009a, 2009b).

The problem of determining the existence of alternating Hamiltonian paths and
cycles in $2$-edge-colored multigraphs is $NP$-complete (Section 16.7 of Bang-
Jensen and Gutin (2009)). There is an extensive literature on alternating
colored trails. Chapter 16 of Bang-Jensen and Gutin (2009) is devoted to the
topic, there is a survey in Kano and Li (2008) and more recent papers include
Abouelaoualim et al. (2008, 2010); Gorbenko and Popov (2012); Gourvès et al.
(2012); Gutin et al. (2017a, b) and Lo (2014a, b, 2016).

It is worthwhile to mention the relationship between directed graphs and
$2$-edge-colored multigraphs for Hamiltonian characterizations. For $2$-edge-
colored multigraphs, two key ingredients are alternating cycle-factors and
color-connectivity. These are the corresponding colored notions of cycle
factors and strong connectivity for digraphs. In fact, many notions and
results on alternating paths and cycles in $2$-edge-colored are analogues of
similar but earlier results on digraphs. In particular, Gutin (1984) was the
first to characterize Hamiltonian bipartite tournaments using strong
connectivity and cycle factors. Saad (1996) was the first to use alternating
cycle factors and color-connectivity and he proved the same result as the
authors but only for $2$-edge-colored complete multigraphs. On the other way,
results on $2$-edge-colored multigraphs had been used to prove results on
digraphs. For example, Häggkvist and Manoussakis (1989) also characterized
Hamiltonian bipartite tournaments, but they used a result on Hamiltonian
cycles in $2$-edge-colored complete graphs by Bánkfalvi and Bánkfalvi (1968).

In Contreras-Balbuena et al. (2017), we gave a sufficient condition for a
$2$-edge-colored multigraph to possess an alternating Hamiltonian cycle. Let
$G$ be a $2$-edge-colored multigraph. An alternating $3$-path $P=(x_{1}$,
$x_{2}$, $x_{3}$, $x_{4})$ is _closed-alternating_ if there exist $y$, $w\in
V(G)$ such that $C=(x_{1}$, $y$, $w$, $x_{4}$, $x_{1})$ is an alternating
cycle. Moreover, if every alternating $3$-path in $G$ is closed-alternanting,
then we say that $G$ is _closed-alternating_. We proved the following result.

######  Theorem 1 (Contreras-Balbuena et al. (2017)).

Let $G$ be a connected $2$-edge-colored multigraph. If $G$ is closed-
alternating and it has an alternating cycle factor, then $G$ has an
alternating Hamiltonian cycle.

##  1 Notation and terminology

For terminology and notation not defined here, we refer the reader to Chapter
16 of Bang-Jensen and Gutin (2009). In this paper, $G=(V(G)$, $E(G))$ denotes
a loopless multigraph. A _$c$ -edge-coloring_ of $G$ is a function $c\colon
E(G)\to\\{1$, …, $c\\}$ and given an edge $[u,v]$ in $G$, its color is denoted
by $c[u$, $v]$. We sometimes refer to $c$-edge-coloring as an _edge-coloring_.
For $2$-edge-colored multigraphs, we use colors blue and red instead of $1$
and $2$. In our figures, the solid edges are blue, the dashed edges are red
and the dash-and-dotted edges are edges with unknown color. Throughout this
paper we only consider $2$-edge-colored multigraphs.

A path (cycle) in a $2$-edge-colored multigraph is _alternating_ if no two
consecutive edges have the same color. A path (cycle) is _Hamiltonian_ if it
visits every vertex in the multigraph. A _cycle factor_ is a collection of
mutually vertex-disjoint cycles that cover all vertices.

Let $G$ be a $2$-edge-colored multigraph, $G$ is _color-connected_ if for
every pair of distinct vertices $x$, $y$ in $G$, there exist alternating $(x$,
$y$)-paths $P$ and $Q$ such that their first edges have different color and
their last edges have different color.

######  Definition 2.

Let $G$ be a $2$-edge-colored multigraph. We say that $G$ is _$2$
-$\mathcal{M}$-closed_ (resp. _$2$ -$\mathcal{NM}$-closed_) if for every
monochromatic (resp. non-monochromatic) $2$-path $P=(x_{1}$, $x_{2}$,
$x_{3})$, there exists an edge between $x_{1}$ and $x_{3}$.

##  2 Main result

In this work we provide the following characterization:

######  Theorem 3.

Let $G$ be a $2$-$\mathcal{M}$-closed multigraph. $G$ has an alternating
Hamiltonian cycle if and only if $G$ is color-connected and has an alternating
cycle factor.

We also provide an infinite family of $2$-$\mathcal{NM}$-closed graphs, color-
connected, with an alternating cycle factor, and with no alternating
Hamiltonian cycle at all.

######  Definition 4.

Let $G$ be a $2$-edge-colored multigraph. Given two alternating cycles
$C_{1}=(x_{1}$, …, $x_{n}$, $x_{1})$, $C_{2}=(y_{1}$, …, $y_{m}$, $y_{1})$ and
an edge $[x_{i}$, $y_{j}]$ between the cycles, we say that $C_{1}$ and $C_{2}$
are _appropriately labelled with respect to $[x_{i}$, $y_{j}]$_ whenever
$c[x_{i}$, $x_{i+1}]=c[y_{j}$, $y_{j+1}]=c[x_{i}$, $y_{j}]$ (see Figure 1).

Figure 1: Appropriately labelled cycles, the solid edges are blue and the
dashed edges are red

In Contreras-Balbuena et al. (2017), we focused on certain pair of edges which
allow us to merge two alternating cycles into one alternating cycle.

######  Proposition 5.

Let $C_{1}=(x_{1}$, …, $x_{n}$, $x_{1})$ and $C_{2}=(y_{1}$, …, $y_{m}$,
$y_{1})$ be two alternating cycles in a $2$-edge-colored multigraph $G$. If
there exist two edges $[x_{i}$, $x_{i+1}]$, $[y_{j}$, $y_{j+1}]$ such that
$(x_{i}$, $y_{j}$, $y_{j+1}$, $x_{i+1}$, $x_{i})$ or $(x_{i}$, $y_{j+1}$,
$y_{j}$, $x_{i+1}$, $x_{i})$ is a monochromatic $4$-cycle, then there exists
an alternating cycle with vertex set $V(C_{1})\cup V(C_{2})$. We call
$[x_{i}$, $x_{i+1}]$, $[y_{j}$, $y_{j+1}]$ a _good pair of edges_.

###### Proof.

If $(x_{i}$, $y_{j}$, $y_{j+1}$, $x_{i+1}$, $x_{i})$ (respectively $(x_{i}$,
$y_{j+1}$, $y_{j}$, $x_{i+1}$, $x_{i})$) is monochromatic, then the
alternating cycle $(x_{i}$, $y_{j}$, $y_{j-1}$, …, $y_{j+2}$, $y_{j+1}$,
$x_{i+1}$, $x_{i+2}$, …, $x_{i-1}$, $x_{i})$ (resp. $(x_{i}$, $y_{j+1}$,
$y_{j+2}$, …, $y_{j-1}$, $y_{j}$, $x_{i+1}$, $x_{i+2}$, …, $x_{i-1}$,
$x_{i})$) merges both cycles. ∎

We will use good pairs of edges extensively throughout this work.

Now, we describe the structure of the arcs between two alternating cycles. Let
$C_{1}=(x_{1}$, …, $x_{n}$, $x_{1})$ and $C_{2}=(y_{1}$, …, $y_{m}$, $y_{1})$
be two alternating cycles in a $2$-$\mathcal{M}$-closed multigraph. If there
exists an edge $[x_{i}$, $y_{j}]$ such that $c[x_{i}$, $x_{i+1}]=c[y_{j}$,
$y_{j+1}]=c[x_{i}$, $y_{j}]$ and there are no good pairs of edges between
$C_{1}$ and $C_{2}$, then we prove that there exists $[x_{i+1}$, $y_{j+1}]$ in
the following lemma. Since there are no good pairs of edges, $[x_{i+1}$,
$y_{j+1}]$ and $[x_{i}$, $y_{j}]$ have different color. Repeating this
procedure, we have all the edges of the form $[x_{i+k},y_{j+k}]$ for any
$k\in\mathbb{Z}$, where the subscripts are taken modulo $n$ and $m$,
respectively. We call these edges _parallel_ edges to the edge $[x_{i}$,
$y_{j}]$.

######  Lemma 6.

Let $G$ be a $2$-$\mathcal{M}$-closed multigraph, and let $C_{1}=(x_{1}$, …,
$x_{n}$, $x_{1})$ and $C_{2}=(y_{1}$, …, $y_{m}$, $y_{1})$ be two alternating
cycles in $G$ with an edge $[x_{i}$, $y_{j}]$ such that $c[x_{i}$,
$x_{i+1}]=c[y_{j}$, $y_{j+1}]=c[x_{i}$, $y_{j}]$ (this is, $C_{1}$ and $C_{2}$
are appropriately labelled with respect to $[x_{i}$, $y_{j}]$). Then
$[x_{i+1}$, $y_{j+1}]$, $[x_{i}$, $y_{j+1}]$ and $[y_{j}$, $x_{i+1}]$ are
edges of $G$ with $c[x_{i+1}$, $y_{j+1}]\neq c[x_{i}$, $y_{j}]$, or there
exists an alternating cycle with vertex set $V(C_{1})\cup V(C_{2})$.

###### Proof.

In what follows, recall that if we find a good pair of edges, we are done
since we can merge both cycles by Proposition 5. So, we suppose that there are
no good pairs of edges.

Assume without loss of generality that $C_{1}$ and $C_{2}$ are appropriately
labelled with respect to $[x_{1}$, $y_{1}]$ and this is a blue edge. Notice
that $(x_{2}$, $x_{1}$, $y_{1})$ and $(x_{1}$, $y_{1}$, $y_{2})$ are
monochromatic $2$-paths, hence $[x_{1}$, $y_{2}]$, $[x_{2}$, $y_{1}]\in E(G)$.
If one of those edges is blue, then $(x_{2}$, $x_{1}$, $y_{2})$ or $(y_{2}$,
$y_{1}$, $x_{2})$ is a monochromatic path, and therefore $[x_{2}$, $y_{2}]\in
E(G)$. If $[x_{2}$, $y_{2}]$ is blue, we are done; otherwise, it is a red edge
and $[x_{1}$, $x_{2}]$, $[y_{1}$, $y_{2}]$ is a good pair of edges. So assume
that $[x_{1}$, $y_{2}]$ and $[x_{2}$, $y_{1}]$ are both red (see Figure 3).

Figure 2: Initial edges in a $2$-$\mathcal{M}$-closed multigraph.

Figure 3: Structure of a $2$-$\mathcal{M}$-closed multigraph (the dash-and-
dotted edges have unknown color.)

Since $(x_{3}$, $x_{2}$, $y_{1})$ and $(y_{3}$, $y_{2}$, $x_{1})$ are
monochromatic, we have that $[x_{1}$, $y_{3}]$, $[x_{3}$, $y_{1}]\in E(G)$.
Similarly, $[x_{n}$, $y_{2}]$, $[y_{m}$, $x_{2}]\in E(G)$. See Figures 3 and
4. Hence, in each of the following cases, either these conditions are met, or
else there is a good pair of edges and an alternating cycle comprising both
sets of vertices.

Case 1. $[x_{1}$, $y_{3}]$ and $[x_{3}$, $y_{1}]$ are red, thus $[x_{n}$,
$y_{3}]$, $[y_{m}$, $x_{3}]\in E(G)$.

Figure 4: Proof of Lemma 6.

If one of the edges $[x_{n}$, $y_{2}]$, $[x_{n}$, $y_{3}]$, $[y_{m}$,
$x_{2}]$, and $[y_{m}$, $x_{3}]$ is red, there exist a good pair of edges in
$G$ (see Figures 6 and 6).

Figure 5: A good pair of edges in Case 1, when $[x_{n},y_{2}]$ is red.

Figure 6: Other good pair of edges in Case 1 when $[x_{n},y_{3}]$ is red.

So assume that $[x_{n}$, $y_{2}]$, $[x_{n}$, $y_{3}]$, $[y_{m}$, $x_{2}]$ and
$[y_{m}$, $x_{3}]$ are blue (see Figure 7).

Figure 7: $[x_{n}$, $y_{2}]$, $[x_{n}$, $y_{3}]$, $[y_{m}$, $x_{2}]$ and
$[y_{m}$, $x_{3}]$ are blue edges. Figure 8: $[x_{n}$, $y_{1}]$ is a red edge.

Therefore $(x_{n}$, $y_{2}$, $y_{1})$ is monochromatic, and hence $[x_{n}$,
$y_{1}]\in E(G)$. We will show that no matter what is the color of the edge
$[x_{n}$, $y_{1}]$, one of the edges $[x_{2}$, $y_{2}]$ and $[x_{n}$, $x_{2}]$
is in $G$. First assume that $[x_{n}$, $y_{1}]$ is red. Since $(x_{n}$,
$y_{1}$, $x_{2})$ is monochromatic, we have that $[x_{n}$, $x_{2}]$ is in $G$
(see Figure 8).

Hence, assume that $[x_{n}$, $y_{1}]$ is blue. Therefore $[x_{n-1}$, $y_{2}]$
and $[x_{n-1}$, $y_{1}]$ are in $G$, since $(x_{n}$, $y_{1}$, $y_{2})$ and
$(x_{n-1}$, $x_{n}$, $y_{1})$ are monochromatic and these edges are red
(otherwise there exist a good pair of edges). Therefore $(x_{2}$, $y_{1}$,
$x_{n-1})$ is a monochromatic path and $[x_{n-1}$, $x_{2}]$ is in $G$. If
$[x_{n-1}$, $x_{2}]$ is red, then $(y_{2}$, $x_{n-1}$, $x_{2})$ is a
monochromatic path, so $[x_{2}$, $y_{2}]\in E(G)$. If $[x_{2}$, $y_{2}]$ is a
blue edge, then $[x_{1}$, $y_{1}]$ and $[x_{2}$, $y_{2}]$ is a good pair of
edges and we can merge both cycles. Otherwise $[x_{n-1}$, $x_{2}]$ is blue,
therefore $(x_{n}$, $x_{n-1}$, $x_{2})$ is monochromatic and $[x_{n}$,
$x_{2}]$ is in $G$. See Figure 10.

Figure 9: $[x_{n}$, $y_{1}]$ is a blue edge.

Figure 10: Alternating cycle in Case 1.

Analogously, no matters the color of the edge $[y_{m}$, $x_{1}]$, we have
$[y_{m}$, $y_{2}]\in E(G)$.

Thus, the edges $[y_{m}$, $y_{2}]$, $[x_{n}$, $x_{2}]$ are in $G$ and both are
red (otherwise $(y_{2}$, $x_{n}$, $x_{2})$ or $(x_{2}$, $y_{m}$, $y_{2})$ are
monochromatic, so $[x_{2}$, $y_{2}]$ will be in $G$). Therefore $(y_{m}$,
$y_{2}$, $y_{1}$, $x_{3}$, $x_{4}$, …, $x_{n}$, $x_{2}$, $x_{1}$, $y_{3}$, …,
$y_{m})$ is an alternating cycle with vertex set $V(C_{1})\cup V(C_{2})$. See
Figure 10.

Case 2. $[x_{1}$, $y_{3}]$ and $[x_{3}$, $y_{1}]$ are not both red. Suppose
without loss of generality that $[x_{3}$, $y_{1}]$ is blue. Therefore
$(y_{2}$, $y_{1}$, $x_{3})$ is monochromatic, and $[x_{3}$, $y_{2}]\in E(G)$.
See Figure 11.

Figure 11: Case 2.

If $[x_{3}$, $y_{2}]$ is red, then $(y_{2}$, $x_{3}$, $x_{2})$ is
monochromatic, and $[x_{2}$, $y_{2}]\in E(G)$. Otherwise, $[x_{3}$, $y_{2}]$
is blue (see Figure 13).

Figure 12: $[x_{3}$, $y_{2}]$ is a blue edge.

Figure 13: Edge $[x_{2}$, $x_{4}]$.

Therefore, $[y_{1}$, $x_{4}]$ is in $G$. If it is blue, then there exist a
good pair of edges $(y_{1}$, $x_{4}$, $x_{3}$, $y_{2}$, $y_{1})$. Hence,
$[y_{1}$, $x_{4}]$ is red. The path $(x_{2}$, $y_{1}$, $x_{4})$ is
monochromatic, thus $[x_{2}$, $x_{4}]\in E(G)$. Then $(x_{4}$, $x_{3}$,
$y_{2})$ is also monochromatic, so $[x_{4}$, $y_{2}]\in E(G)$. If $[x_{4}$,
$y_{2}]$ is blue, we have a good pair of edges. Hence, it is red (see Figure
13).

If $[x_{2}$, $x_{4}]$ is red, then $(x_{2}$, $x_{4}$, $y_{2})$ is a
monochromatic path, $[x_{2}$, $y_{2}]\in E(G)$ and we are done. Therefore,
$[x_{2}$, $x_{4}]$ is blue and $(x_{4}$, $x_{2}$, $x_{3}$, $y_{2}$, $y_{3}$,
…, $y_{1}$, $x_{1}$, $x_{n}$, …, $x_{4})$ is an alternating cycle with vertex
set $V(C_{1})\cup V(C_{2})$.

In all these cases, we have that the edge $[x_{2}$, $y_{2}]$ is in $G$ or
there exists an alternating cycle with vertex set $V(C_{1})\cup V(C_{2})$. ∎

######  Corollary 7.

Let $C_{1}=(x_{1}$, …, $x_{n}$, $x_{1})$ and $C_{2}=(y_{1}$, …, $y_{m}$,
$y_{1})$ be two alternating cycles in a $2$-$\mathcal{M}$-closed graph. If
there exists an edge between $C_{1}$ and $C_{2}$, then at least one of the
following holds:

  1. 1.

There exists an alternating cycle with vertex set $V(C_{1})\cup V(C_{2})$.

  2. 2.

$[x$, $y]\in E(G)$ for every $x\in C_{1}$ and $y\in C_{2}$.

###### Proof.

We can assume that between $C_{1}$ and $C_{2}$ there is no good pair of edges
(otherwise, we are done since we can merge both cycles by Proposition 5).
Notice that Lemma 6 states, in this situation, that if
$(x_{i-1},x_{i},y_{j},y_{j+1})$ is a monochromatic path between $C_{1}$ and
$C_{2}$, then $[x_{i-1},y_{j+1}]$ exists and $c[x_{i-1},y_{j+1}]\neq
c[x_{i},y_{j}]$.

Suppose that $[x_{1},y_{j}]$ is an edge in $G$, we will prove that
$[x_{1},y_{j+1}]$ is an edge in $G$. Since we can interchange $C_{1}$ and
$C_{2}$ and repeat this procedure, we will obtain that $[x,y]\in E(G)$ for
every $x\in C_{1}$ and $y\in C_{2}$. We consider the following cases:

Case 1. $c[x_{1},y_{j}]=c[y_{j},y_{j+1}]$. Then $(x_{1},y_{j},y_{j+1})$ is a
monochromatic path. Therefore $[x_{1},y_{j+1}]$ is an edge of $G$.

Case 2. $c[x_{1},y_{j}]\neq c[y_{j},y_{j+1}]$. Suppose without loss of
generality that $c[x_{1},x_{2}]$ is blue.

Case 2.1 $c[x_{1},y_{j}]$ is red and $c[y_{j},y_{j+1}]$ is blue. Then
$c[x_{1},x_{n}]$ and $c[y_{j},y_{j-1}]$ are red edges. Since
$(x_{n},x_{1},y_{j},y_{j-1})$ is a (monochromatic) red path, Lemma 6 implies
that $[x_{n},y_{j-1}]$ is a blue edge in $G$. Now,
$(x_{n-1},x_{n},y_{j-1},y_{j-2})$ is a (monochromatic) blue path, so we have
that $[x_{n-1},y_{j-2}]$ is a red edge in $G$. Continuing this way, we obtain
that $[x_{1-i},y_{j-i}]$ is an edge in $G$ for every $i\in\mathbb{N}$, where
the subscripts are taken modulo $n$ and $m$, respectively. Applying Lemma 6 to
edges $[x_{1-(i+1)},x_{1-i}]$, $[x_{1-i},y_{j-i}]$ and
$[y_{j-(i+1)},y_{j-i}]$, we have that $[x_{1-(i+1)},y_{j-i}]\in E(G)$.
Therefore for $i=nm-1$, $[x_{1-((nm-1)+1)},y_{j-(nm-1)}]$ is in $G$, but
$[x_{1-((nm-1)+1)},y_{j-(nm-1)}]=[x_{1},y_{j+1}]$ since the subscripts are
taken modulo $n$ and $m$, respectively.

Case 2.2 $c[x_{1},y_{j}]$ is blue and $c[y_{j},y_{j+1}]$ is red. Then
$c[y_{j},y_{j-1}]$ is blue. Since $(x_{2},x_{1},y_{j},y_{j-1})$ is a
(monochromatic) blue path, Lemma 6 implies that $[x_{2},y_{j-1}]$ is a red
edge. Now, $(x_{3},x_{2},y_{j-1},y_{j-2})$ is a (monochromatic) red path, so
we have that $[y_{j-1},y_{j-2}]$, $[x_{3},y_{j-2}]$ is a blue edge. Continuing
this way, we obtain that $[x_{1+i},y_{j-i}]$ is an edge in $G$ for every
$i\in\mathbb{N}$, where the subscripts are taken modulo $n$ and $m$,
respectively. Applying Lemma 6 to edges $[x_{1+(i+1)},x_{1+i}]$,
$[x_{1+i},y_{j-i}]$ and $[y_{j-(i+1)},y_{j-i}]$, we have that
$[x_{1+(i+1)},y_{j-i}]\in E(G)$. Therefore for $i=nm-1$,
$[x_{1+(nm-1)+1},y_{j-(nm-1)}]$ is in $G$, but
$[x_{1+(nm-1)+1},y_{j-(nm-1)}]=[x_{1},y_{j+1}]$ since the subscripts are taken
modulo $n$ and $m$, respectively. ∎

Let $C$ be a cycle in $G$. We denote by $I_{C}$ (resp. $P_{C}$) the set of
vertices with odd (resp. even) subscript in $C$.

######  Definition 8.

Let $C_{1}$ and $C_{2}$ be two disjoint alternating cycles in a
$2$-$\mathcal{M}$-closed graph $G$. We will say that _$C_{1}$ blue-dominates_
(resp. _red-dominates) $C_{2}$_ whenever the following conditions are
satisfied:

  * •

$[x$, $y]\in E(G)$ for every $x\in C_{1}$ and $y\in C_{2}$.

  * •

$G[I_{C_{1}}]$ and $G[P_{C_{1}}]$ are complete graphs.

  * •

All the edges in $G[I_{C_{1}}]$ are blue (resp. red).

  * •

All the edges in $G[P_{C_{1}}]$ are red (resp. blue).

  * •

All the edges between $I_{C_{1}}$ and $C_{2}$ are blue (resp. red).

  * •

All the edges between $P_{C_{1}}$ and $C_{2}$ are red (resp. blue).

Figure 14: $C_{1}$ blue-dominates $C_{2}$.

See Figure 14. Whenever $C_{1}$ blue-dominates or red-dominates $C_{2}$, we
say that $C_{1}$ _color-dominates_ $C_{2}$.

We will make use of some concepts about digraphs. The vertex set and the arc
set of a digraph $D$ are denoted by $V(D)$ and $A(D)$, respectively. A digraph
for which there exists exactly one arc between each pair of vertices is a
_tournament_. An arc $(u,v)\in A(D)$ is _symmetric_ if $(v,u)\in A(D)$;
otherwise, it is _asymmetric_. A digraph $D$ is _quasi-transitive_ if $u$ and
$w$ are adjacent whenever $(u$, $v)$, $(v$, $w)\in A(D)$ and it is a _local
tournament_ if there is exactly one arc between $u$ and $w$ whenever $(u$,
$v)$, $(w$, $v)\in A(D)$ or $(v$, $u)$, $(v$, $w)\in A(D)$. For digraphs with
no symmetric arcs, the intersection of quasi-transitive digraphs and local
tournaments is precisely the class of tournaments (see Chapter 2 of Bang-
Jensen and Gutin (2009)). A digraph $D$ is _acyclic_ if it has no directed
cycles.

Now, we will prove the main theorem.

######  Theorem 9.

Let $G$ be a $2$-$\mathcal{M}$-closed graph. $G$ has an alternating
Hamiltonian cycle if and only if it is color-connected and has an alternating
cycle factor.

###### Proof.

If $G$ is a $2$-$\mathcal{M}$-closed graph and has an alternating Hamiltonian
cycle, then $G$ is color-connected and has an alternating cycle factor. So,
let $G$ be a $2$-$\mathcal{M}$-closed and color-connected graph. Given any
alternating cycle factor of $G$ with at least two cycles, $C=\\{C_{1}$, …,
$C_{l}\\}$, we will construct a smaller alternating cycle factor. Since $G$ is
connected, there exist two alternating cycles $C_{1}=(x_{1}$, …, $x_{n}$,
$x_{1})$ and $C_{2}=(y_{1}$, …, $y_{m}$, $y_{1})$ with an edge between them.
Suppose without loss of generality that $[x_{1}$, $y_{1}]\in E(G)$, it is blue
and that $C_{1}$ and $C_{2}$ are appropriately labelled with respect to
$[x_{1}$, $y_{1}]$. Proposition 5 implies that if there exists a good pair of
edges, then we can merge both cycles, obtaining a smaller alternating cycle
factor. So, we can assume that there is no good pair of edges and Corollary 7
implies that $[x$, $y]\in E(G)$ for every $x\in C_{1}$ and $y\in C_{2}$. Also,
this implies that consecutive parallel edges between $C_{1}$ and $C_{2}$ have
different color. Now, we analyze the color structure of the set of edges
between $x_{1}$ and $C_{2}$.

Case 1. There are blue and red edges between $x_{1}$ and $I_{C_{2}}$. We can
suppose that $[x_{1}$, $x_{2}]$, $[y_{1}$, $y_{2}]$, $[x_{1}$, $y_{1}]$ are
blue, and $[x_{1}$, $y_{3}]$ is red. Since parallel edges between $C_{1}$ and
$C_{2}$ have alternating colors (otherwise there exists a good pair of edges),
we have that

$(y_{1},y_{2},x_{2},x_{1},y_{3},y_{4},x_{4},x_{3},\ldots,y_{n},x_{n},x_{n-1},y_{n+1},y_{n+2},\ldots,y_{m},y_{1})\text{,}$

when $n\leq m$, or

$(y_{1},y_{2},x_{2},x_{1},y_{3},y_{4},x_{4},x_{3},\ldots,y_{m-2},x_{m-2},x_{m-3},y_{m-1},y_{m},x_{n},x_{n-1},\ldots,x_{m},x_{m-1},y_{1})\text{,}$

when $n>m$ (notice that arc $[x_{m-1}$, $y_{1}]$ is parallel to $[x_{1}$,
$y_{3}]$), is an alternating cycle with vertex set $V(C_{1})\cup V(C_{2})$
(see Figure 15).

Figure 15: Case 1.

Case 2. There are blue and red edges between $x_{1}$ and $P_{C_{2}}$. Without
loss of generality, assume that $[x_{1}$, $y_{k}]$ is a red edge and $[x_{1}$,
$y_{k+2}]$ is a blue edge, for some even integer $k$. Recall that $[x_{1}$,
$x_{2}]$ and $[y_{k+1}$, $y_{k+2}]$ are blue edges. Since parallel edges
between $C_{1}$ and $C_{2}$ have alternating colors, we have that $[x_{2}$,
$y_{k+1}]$ is a blue edge. Therefore, $[x_{1}$, $x_{2}]$, $[y_{k+1}$,
$y_{k+2}]$ is a good pair of edges.

Case 3. All the edges between $x_{1}$ and $I_{C_{2}}$ and all the edges
between $x_{1}$ and $P_{C_{2}}$ have the same color. First assume that the
edges between $x_{1}$ and $C_{2}$ are not monochromatic, this implies that the
edges between $x_{1}$ and $I_{C_{2}}$ are blue and the edges between $x_{1}$
and $P_{C_{2}}$ are red (see Figure 16). Since the colors of consecutive
parallel edges between $C_{1}$ and $C_{2}$ are alternating, we have that all
the edges between $x_{2}$ and $I_{C_{2}}$ are blue and the edges between
$x_{2}$ and $P_{C_{2}}$ are red. And so on. Therefore, all the edges between
$y_{1}$ and $C_{1}$ are blue. Interchanging $C_{1}$ and $C_{2}$, we can always
assume that all the edges between $x_{1}$ and $C_{2}$ have the same color.

Figure 16: Case 3, first assumption.

Suppose without loss of generality that all the edges between $x_{1}$ and
$C_{2}$ are blue (see Figure 17). Since the colors of the parallel edges
between $C_{1}$ and $C_{2}$ are alternating, the edges between $x_{2}$ and
$C_{2}$ are all red. Therefore all the edges between $P_{C_{1}}$ and $C_{2}$
are red and all the edges between $I_{C_{1}}$ and $C_{2}$ are blue.

Figure 17: Case 3, second assumption.

These conditions fix the edges between $C_{1}$ and $C_{2}$. Notice that
$(x_{2i+1}$, $y_{j}$, $x_{2k+1})$ and $(x_{2i}$, $y_{j}$, $x_{2k})$ are
monochromatic paths for every $i$, $k\in\mathbb{Z}$, where $i$ and $k$ are
taken modulo $n$. Therefore, $[x_{2i+1}$, $x_{2k+1}]$, $[x_{2i}$, $x_{2k}]\in
E(G)$. Now, we will analyze the structure inside the cycle $C_{1}$.

Case 3.1 $[x_{2k_{1}+1}$, $x_{2k_{2}+1}]$ is a red edge or $[x_{2k_{3}}$,
$x_{2k_{4}}]$ is a blue edge (recall that $x_{2k_{1}+1}$, $x_{2k_{2}+1}\in
I_{C_{1}}$ and $x_{2k_{3}}$, $x_{2k_{4}}\in P_{C_{1}}$).

Suppose that $2k_{1}+1<2k_{2}+1$. If $[x_{2k_{1}+1}$, $x_{2k_{2}+1}]$ is a red
edge, then there exist an alternating cycle merging both cycles $(y_{1}$,
$x_{2k_{1}}$, $x_{2k_{1}-1}$, …, $x_{2k_{2}+1}$, $x_{2k_{1}+1}$,
$x_{2k_{1}+2}$, …, $x_{2k_{2}}$, $y_{m}$, $y_{m-1}$, …, $y_{1})$. Analogously
if $[x_{2k_{3}}$, $x_{2k_{4}}]$ is blue.

Case 3.2 All the edges between vertices in $I_{C_{1}}$ are blue, and all the
edges between vertices in $P_{C_{1}}$ are red. Therefore, $C_{1}$ blue-
dominates $C_{2}$.

Notice that if $C_{i}$ does not color-dominate $C_{j}$ and $C_{j}$ does not
color-dominate $C_{i}$, we can reduce the number of cycles in the alternating
cycle factor. Therefore, in a minimum alternating cycle factor, $C_{i}$ color-
dominates $C_{j}$ or $C_{j}$ color-dominates $C_{i}$ for every pair of
adjacent cycles in such factor.

So, given an alternating cycle factor $C$, we can reduce the number of cycles
in $C$ or between every pair $C_{i}$ and $C_{j}$ of adjacent cycles in $C$,
$C_{i}$ color-dominates $C_{j}$ or $C_{j}$ color-dominates $C_{i}$.

Let $C=\\{C_{1}$, …, $C_{l}\\}$ be a minimum alternating cycle factor of $G$,
where $C_{i}=(x_{1,i}$, $x_{2,i}$, $x_{3,i}$, …, $x_{m_{i},i}$, $x_{1,i})$,
where $m_{i}$ is the length of $C_{i}$, for every $i\in\\{1$, …, $l\\}$. We
define the colored digraph $D_{G_{C}}^{*}$ as follows:

  * •

$V(D_{G_{C}}^{*})=C$, and

  * •

$(C_{i}$, $C_{j})\in A(D_{G_{C}}^{*})$ if and only if $C_{i}$ color-dominates
$C_{j}$. Moreover, $c[C_{i}$, $C_{j}]=c[x_{1,i}$, $x_{1,j}]$. This is, arcs
have the same color as the color-domination between $C_{i}$ and $C_{j}$.

Let us suppose that $C_{1}$ blue-dominates $C_{2}$ and that the first edge of
$C_{1}$ (i.e., $[x_{1,1}$, $x_{2,1}]$) is red. The cycle
$C_{1}^{rev}=(x_{1,1}$, $x_{m_{i},1}$, …, $x_{2,1}$, $x_{1,1})$ is the
_reverse_ of $C_{1}$. Notice that $I_{C_{1}}=I_{C_{1}^{rev}}$ and
$P_{C_{1}}=P_{C_{1}^{rev}}$. Hence, $C_{1}^{rev}$ also blue-dominates $C_{2}$
and the first edge of $C_{1}^{rev}$ is blue. Therefore, without loss of
generality, we can always choose the color of the first edge of each cycle.

Now, we will prove that $D_{G_{C}}^{*}$ is an acyclic tournament. Let
$C^{\prime}=(C_{1}$, $C_{2}$, …, $C_{p}$, $C_{1})$ be a cycle of minimum
length in $V(D_{G_{C}}^{*})$. If $p=2$, then all the edges between $x_{1,1}$
and $C_{2}$ are monochromatic, and all the edges between $x_{1,2}$ and $C_{1}$
are also monochromatic; moreover, all those edges have the same color. Hence,
if $C_{1}$ blue-dominates $C_{2}$, then $C_{2}$ blue-dominates $C_{1}$. Assume
without loss of generality that the first edges of $C_{1}$ and $C_{2}$ are
blue. Therefore $[x_{1,1}$, $x_{2,1}]$ and $[x_{1,2}$, $x_{2,2}]$ is a good
pair of edges between $C_{1}$ and $C_{2}$, so we can merge both alternating
cycles and reduce the number of cycles in $C$, which is a contradiction. Thus,
we can assume that $p\geq 3$.

We will show that $p=3$. Assume that $p>3$. Since $(C_{1}$, $C_{2})$ and
$(C_{2}$, $C_{3})$ are arcs in $D_{G_{C}}^{*}$, we have that $C_{1}$ color-
dominates $C_{2}$ and $C_{2}$ color-dominates $C_{3}$. Therefore, there exists
a monochromatic path $(x_{a,1}$, $x_{b,2}$, $x_{c,3})$ in $G$ and we have an
edge between $C_{1}$ and $C_{3}$. Moreover, there exists an arc between
$C_{1}$ and $C_{3}$ in $D_{G_{C}}^{*}$. If $(C_{3}$, $C_{1})\in
A(D_{G_{C}}^{*})$, we are done. So we have that $(C_{1}$, $C_{3})$ is an arc
in $A(D_{G_{C}}^{*})$, which is a contradiction with the minimality of
$C^{\prime}$. Let $(C_{1}$, $C_{2}$, $C_{3}$, $C_{1})$ be the minimum cycle in
$D_{G_{C}}^{*}$. We consider two possibilities, either $(C_{1}$, $C_{2}$,
$C_{3}$, $C_{1})$ is monochromatic or not.

Case 3.2.1 $(C_{1}$, $C_{2}$, $C_{3}$, $C_{1})$ is monochromatic. Assume
without loss of generality that $C_{i}$ blue-dominates $C_{i+1}$ and,
moreover, that $[x_{1,i}$, $x_{2,i}]$ is a blue edge, where the subscripts are
taken modulo $3$. Recall that all the edges between $x_{1,i}$ and $C_{i+1}$
are blue and all the edges between $x_{m_{3},3}$ and $C_{1}$ are red. Hence,
$(x_{1,1}$, $x_{2,1}$, …, $x_{m_{1},1}$, $x_{1,2}$, $x_{2,2}$, …,
$x_{m_{2},2}$, $x_{1,3}$, $x_{2,3}$, …, $x_{m_{3},3}$, $x_{1,3}$, $x_{2,3}$,
…, $x_{m_{3},3}$, $x_{1,1})$ is an alternating cycle.

Case 3.2.2 $(C_{1}$, $C_{2}$, $C_{3}$, $C_{1})$ is not monochromatic. Assume
without loss of generality that $C_{1}$ blue-dominates $C_{2}$, $C_{2}$ blue-
dominates $C_{3}$ and $C_{3}$ red-dominates $C_{1}$. Moreover, assume that
$[x_{1,i}$, $x_{2,i}]$ is a blue edge, for $i\in\\{1$, $2\\}$ and a red edge,
for $i=3$. Recall that all the edges between $x_{1,i}$ and $C_{i+1}$ are blue,
for $i\in\\{1$, $2\\}$ and all the edges between $x_{1,3}$ and $C_{1}$ are
red. Hence, $(x_{1,1}$, $x_{2,1}$, …, $x_{m_{1},1}$, $x_{1,2}$, $x_{2,2}$, …,
$x_{m_{2},2}$, $x_{m_{3},3}$, $x_{m_{3}-1,3}$, …, $x_{2,3}$, $x_{1,3}$,
$x_{1,1})$ is an alternating cycle.

In both cases, we obtain an alternating cycle with vertex set $V(C_{1})\cup
V(C_{2})\cup V(C_{3})$, which is a contradiction to the choice of $C$.
Therefore, $D_{G_{C}}^{*}$ is an acyclic digraph. Moreover, the previous
argument also shows that $D_{G_{C}}^{*}$ is a quasi-transitive digraph.

Now, let us show that for $C_{i}$, $C_{j}$ and $C_{k}$, if we have $(C_{i}$,
$C_{j})$ and $(C_{i}$, $C_{k})$ are arcs in $D_{G_{C}}^{*}$. Then $c[C_{i}$,
$C_{j}]=c[C_{i}$, $C_{k}]$. Assume on the contrary that $c[C_{i}$, $C_{j}]\neq
c[C_{i}$, $C_{k}]$. Suppose without loss of generality that $C_{i}$ red-
dominates $C_{j}$ and that $C_{i}$ blue-dominates $C_{k}$. The definition of
domination implies that all the edges between vertices in $I_{C_{i}}$ are red
and are also blue, which is a contradiction.

Let $(C_{i}$, $C_{j})$ and $(C_{i}$, $C_{k})$ be arcs in $D_{G_{C}}^{*}$. We
know that $c[C_{i}$, $C_{j}]=c[C_{i}$, $C_{k}]$, so $(x_{1,j}$, $x_{1,i}$,
$x_{1,k})$ is monochromatic path. Therefore, $(C_{j}$, $C_{k})$ or $(C_{k}$,
$C_{j})$ is in $A(D_{G_{C}}^{*})$. Analogously, if $(C_{j}$, $C_{i})$ and
$(C_{k}$, $C_{i})$ are arcs in $D_{G_{C}}^{*}$, we have that $(C_{j}$,
$C_{k})$ or $(C_{k}$, $C_{j})$ is in $A(D_{G_{C}}^{*})$. Therefore
$D_{G_{C}}^{*}$ is a local tournament.

Since $G$ is a connected graph and $D_{G_{C}}^{*}$ is both a quasi-transitive
digraph and a local tournament, we have that $D_{G_{C}}^{*}$ is an acyclic
tournament (recall that there is no symmetric arcs in $D_{G_{C}}^{*}$).
Therefore, there exists a vertex of out-degree $l-1$. Assume without loss of
generality that this vertex is $C_{1}$, so we have $(C_{1}$, $C_{i})\in
A[D_{G_{C}}^{*}]$ for every $i\in\\{2$, $3$, …, $l\\}$. Moreover, all these
arcs have the same color, let it be blue. Therefore $C_{1}$ blue-dominates
every other cycle in $D_{G_{C}}^{*}$, as it is depicted in Figure 19.
Therefore, $G$ is not color-connected (since every vertex in $I_{C_{1}}$ does
not have any alternating path starting with a red edge to any vertex in
$V(G-C_{1})$), which is a contradiction.

Figure 18: $G$ is not color-connected.

Figure 19: Counterexample.

∎

To be color-connected and to have an alternating cycle factor are necessary
conditions for a graph to have an alternating Hamiltonian cycle. Nevertheless,
these conditions are insufficient for the $2$-$\mathcal{NM}$-closed graphs. In
Figure 19, we show a $2$-$\mathcal{NM}$-closed and color-connected graph, with
an alternating cycle factor and with no alternating Hamiltonian cycles at all.

Moreover, we can construct a family of such graphs. If we take two alternating
cycles $C_{1}$, $C_{2}$ in which all the edges inside of them are red, and we
“paste” the cycles taking $x_{1}$, $x_{2}\in V(C_{1})$ and $y_{1}$, $y_{2}\in
V(C_{2})$ such that $[x_{1}$, $x_{2}]$, $[y_{1}$, $y_{2}]$ are blue, and we
only add the red edges $[x_{1}$, $y_{1}]$, $[x_{2}$, $y_{2}]$, $[x_{1}$,
$y_{2}]$ and $[x_{2}$, $y_{1}]$, then we obtain a graph which is color-
connected and has alternating cycle factor, but that cannot be merged in order
to obtain an alternating cycle (see Figure 20).

Figure 20: Family with no alternating Hamiltonian cycles at all.

## Acknowledgments

The authors are very grateful to the anonymous referees for a thorough review
and their helpful suggestions which improved substantially the writing of this
paper.

## References

  * Abouelaoualim et al. (2008) A. Abouelaoualim, K. C. Das, L. Faria, Y. Manoussakis, C. Martinhon, and R. Saad.  Paths and trails in edge-colored graphs.  _Theoret. Comput. Sci._ , 409(3):497–510, 2008\.  ISSN 0304-3975.  10.1016/j.tcs.2008.09.021.  URL https://doi.org/10.1016/j.tcs.2008.09.021.
  * Abouelaoualim et al. (2010) A. Abouelaoualim, K. C. Das, W. Fernandez de la Vega, M. Karpinski, Y. Manoussakis, C. A. Martinhon, and R. Saad.  Cycles and paths in edge-colored graphs with given degrees.  _J. Graph Theory_ , 64(1):63–86, 2010.  ISSN 0364-9024.  10.1002/jgt.20440.  URL https://doi.org/10.1002/jgt.20440.
  * Alizadeh et al. (1995) F. Alizadeh, R. M. Karp, L. A. Newberg, and D. K. Weisser.  Physical mapping of chromosomes: a combinatorial problem in molecular biology.  _Algorithmica_ , 13(1-2):52–76, 1995.  ISSN 0178-4617.  10.1007/BF01188581.  URL https://doi.org/10.1007/BF01188581.
  * Bang-Jensen and Gutin (1997) J. Bang-Jensen and G. Gutin.  Alternating cycles and paths in edge-coloured multigraphs: a survey.  _Discrete Math._ , 165/166:39–60, 1997.  ISSN 0012-365X.  10.1016/S0012-365X(96)00160-4.  URL https://doi.org/10.1016/S0012-365X(96)00160-4.  Graphs and combinatorics (Marseille, 1995).
  * Bang-Jensen and Gutin (2009) J. Bang-Jensen and G. Gutin.  _Digraphs_.  Springer Monographs in Mathematics. Springer-Verlag London, Ltd., London, second edition, 2009.  ISBN 978-1-84800-997-4.  10.1007/978-1-84800-998-1.  URL https://doi.org/10.1007/978-1-84800-998-1.  Theory, algorithms and applications.
  * Bánkfalvi and Bánkfalvi (1968) M. Bánkfalvi and Z. Bánkfalvi.  Alternating Hamiltonian circuit in two-coloured complete graphs.  In _Theory of Graphs (Proc. Colloq., Tihany, 1966)_ , pages 11–18. Academic Press, New York, 1968.
  * Chou et al. (1994) W. S. Chou, Y. Manoussakis, O. Megalakaki, M. Spyratos, and Z. Tuza.  Paths through fixed vertices in edge-colored graphs.  _Math. Inform. Sci. Humaines_ , 127:49–58, 1994.  ISSN 0995-2314.
  * Contreras-Balbuena et al. (2017) A. Contreras-Balbuena, H. Galeana-Sánchez, and I. A. Goldfeder.  A new sufficient condition for the existence of alternating Hamiltonian cycles in 2-edge-colored multigraphs.  _Discrete Appl. Math._ , 229:55–63, 2017.  ISSN 0166-218X.  10.1016/j.dam.2017.04.033.  URL https://doi.org/10.1016/j.dam.2017.04.033.
  * Dorninger (1987) D. Dorninger.  On permutations of chromosomes.  In _Contributions to general algebra, 5 (Salzburg, 1986)_ , pages 95–103. Hölder-Pichler-Tempsky, Vienna, 1987.
  * Dorninger (1994) D. Dorninger.  Hamiltonian circuits determining the order of chromosomes.  _Discrete Appl. Math._ , 50(2):159–168, 1994\.  ISSN 0166-218X.  10.1016/0166-218X(92)00171-H.  URL https://doi.org/10.1016/0166-218X(92)00171-H.
  * Dorninger and Timischl (1987) D. Dorninger and W. Timischl.  Geometrical constraints on bennett’s predictions of chromosome order.  _Heredity_ , 59(3):321–325, 1987.  ISSN 1365-2540.  10.1038/hdy.1987.138.  URL http://dx.doi.org/10.1038/hdy.1987.138.
  * Gorbenko and Popov (2012) A. Gorbenko and V. Popov.  The Hamiltonian alternating path problem.  _IAENG Int. J. Appl. Math._ , 42(4):204–213, 2012\.  ISSN 1992-9978.
  * Gourvès et al. (2010) L. Gourvès, A. Lyra, C. Martinhon, and J. Monnot.  The minimum reload $s$-$t$ path, trail and walk problems.  _Discrete Appl. Math._ , 158(13):1404–1417, 2010\.  ISSN 0166-218X.  10.1016/j.dam.2010.03.009.  URL https://doi.org/10.1016/j.dam.2010.03.009.
  * Gourvès et al. (2012) L. Gourvès, A. Lyra, C. A. Martinhon, and J. Monnot.  On paths, trails and closed trails in edge-colored graphs.  _Discrete Math. Theor. Comput. Sci._ , 14(2):57–74, 2012.  ISSN 1365-8050.
  * Gutin (1984) G. Gutin.  Criterion for complete bipartite digraphs to be Hamiltonian.  _Vestsī Akad. Navuk BSSR Ser. Fīz.-Mat. Navuk_ , 1:109–110, 1984.  ISSN 0002-3574.
  * Gutin et al. (2017a) G. Gutin, M. Jones, B. Sheng, M. Wahlström, and A. Yeo.  Chinese postman problem on edge-colored multigraphs.  _Discrete Appl. Math._ , 217(part 2):196–202, 2017a.  ISSN 0166-218X.  10.1016/j.dam.2016.08.005.  URL https://doi.org/10.1016/j.dam.2016.08.005.
  * Gutin et al. (2017b) G. Gutin, M. Jones, B. Sheng, M. Wahlström, and A. Yeo.  Acyclicity in edge-colored graphs.  _Discrete Math._ , 340(2):1–8, 2017b.  ISSN 0012-365X.  10.1016/j.disc.2016.07.012.  URL https://doi.org/10.1016/j.disc.2016.07.012.
  * Häggkvist and Manoussakis (1989) R. Häggkvist and Y. Manoussakis.  Cycles and paths in bipartite tournaments with spanning configurations.  _Combinatorica_ , 9(1):33–38, 1989.  ISSN 0209-9683.  10.1007/BF02122681.  URL https://doi.org/10.1007/BF02122681.
  * Kano and Li (2008) M. Kano and X. Li.  Monochromatic and heterochromatic subgraphs in edge-colored graphs—a survey.  _Graphs Combin._ , 24(4):237–263, 2008.  ISSN 0911-0119.  10.1007/s00373-008-0789-5.  URL https://doi.org/10.1007/s00373-008-0789-5.
  * Lo (2014a) A. Lo.  A Dirac type condition for properly coloured paths and cycles.  _J. Graph Theory_ , 76(1):60–87, 2014a.  ISSN 0364-9024.  10.1002/jgt.21751.  URL https://doi.org/10.1002/jgt.21751.
  * Lo (2014b) A. Lo.  An edge-colored version of Dirac’s theorem.  _SIAM J. Discrete Math._ , 28(1):18–36, 2014b.  ISSN 0895-4801.  10.1137/120903750.  URL https://doi.org/10.1137/120903750.
  * Lo (2016) A. Lo.  Properly coloured Hamiltonian cycles in edge-coloured complete graphs.  _Combinatorica_ , 36(4):471–492, 2016.  ISSN 0209-9683.  10.1007/s00493-015-3067-1.  URL https://doi.org/10.1007/s00493-015-3067-1.
  * Petersen (1891) J. Petersen.  Die Theorie der regulären graphs.  _Acta Math._ , 15(1):193–220, 1891.  ISSN 0001-5962.  10.1007/BF02392606.  URL https://doi.org/10.1007/BF02392606.
  * Pevzner (1995) P. A. Pevzner.  DNA physical mapping and alternating Eulerian cycles in colored graphs.  _Algorithmica_ , 13(1-2):77–105, 1995.  ISSN 0178-4617.  10.1007/BF01188582.  URL https://doi.org/10.1007/BF01188582.
  * Saad (1996) R. Saad.  Finding a longest alternating cycle in a $2$-edge-coloured complete graph is in RP.  _Combin. Probab. Comput._ , 5(3):297–306, 1996\.  ISSN 0963-5483.  10.1017/S0963548300002054.  URL https://doi.org/10.1017/S0963548300002054.
  * Wirth and Steffan (2001) H.-C. Wirth and J. Steffan.  Reload cost problems: minimum diameter spanning tree.  _Discrete Appl. Math._ , 113(1):73–85, 2001.  ISSN 0166-218X.  10.1016/S0166-218X(00)00392-9.  URL https://doi.org/10.1016/S0166-218X(00)00392-9.  25th International Workshop on Graph-Theoretic Concepts in Computer Science (WG’99) (Ascona).
  * Xu et al. (2009a) H. Xu, K. W. Li, K. W. Hipel, and D. M. Kilgour.  A matrix approach to status quo analysis in the graph model for conflict resolution.  _Appl. Math. Comput._ , 212(2):470–480, 2009a.  ISSN 0096-3003.  10.1016/j.amc.2009.02.051.  URL https://doi.org/10.1016/j.amc.2009.02.051.
  * Xu et al. (2009b) H. Xu, K. W. Li, D. M. Kilgour, and K. W. Hipel.  A matrix-based approach to searching colored paths in a weighted colored multidigraph.  _Appl. Math. Comput._ , 215(1):353–366, 2009b.  ISSN 0096-3003.  10.1016/j.amc.2009.04.086.  URL https://doi.org/10.1016/j.amc.2009.04.086.
  * Xu et al. (2010) H. Xu, D. M. Kilgour, K. W. Hipel, and G. Kemkes.  Using matrices to link conflict evolution and resolution in a graph model.  _European J. Oper. Res._ , 207(1):318–329, 2010\.  ISSN 0377-2217.  10.1016/j.ejor.2010.03.025.  URL https://doi.org/10.1016/j.ejor.2010.03.025.