# ZTCloudGuard: Zero Trust Context-Aware Access Management Framework to Avoid
Misuse Cases in the Era of Generative AI and Cloud-based Health Information
Ecosystem

Khalid Al-hammuri  Fayez Gebali  Awos Kanan

###### Abstract

Managing access between large numbers of distributed medical devices has
become a crucial aspect of modern healthcare systems, enabling the
establishment of smart hospitals and telehealth infrastructure. However, as
telehealth technology continues to evolve and Internet of Things (IoT) devices
become more widely used, they are also becoming increasingly exposed to
various types of vulnerabilities and medical errors. In healthcare information
systems, about 90% of vulnerabilities emerged from misuse cases and human
errors. As a result, there is a need for additional research and development
of security tools to prevent such attacks. This article proposes a zero-trust-
based context-aware framework for managing access to the main components of
the cloud ecosystem, including users, devices and output data. The main goal
and benefit of the proposed framework is to build a scoring system to prevent
or alleviate misuse cases while using distributed medical devices in cloud-
based healthcare information systems. The framework has two main scoring
schemas to maintain the chain of trust. First, it proposes a critical trust
score based on cloud-native micro-services of authentication, encryption,
logging, and authorizations. Second, creating a bond trust scoring to assess
the real-time semantic and syntactic analysis of attributes stored in a
healthcare information system. The analysis is based on a pre-trained machine
learning model to generate the semantic and syntactic scores. The framework
also takes into account regulatory compliance and user consent to create a
scoring system. The advantage of this method is that it is applicable to any
language and adapts to all attributes as it relies on a language model, not
just a set of predefined and limited attributes. The results show a high $F1$
score of 93.5%, which proves that it is valid for detecting misuse cases.

###### keywords:

Access management, zero-trust, distributed medical devices, cloud, health
information system, misuse cases , IoT.

††journal: arXiv

[first]organization=University of Victoria,Electrical and Computer Engineering
addressline=Finnerty Rd., city=Victoria, postcode=V8W 2Y2, state=BC,
country=Canada

[second]organization=Princess Sumaya University for Technology, Computer
Engineering addressline=Khalil Saket Street Al-Jubaiha, city=Amman,
postcode=11941, state=Amman, country=Jordan

##  1 Introduction

Problem statement: The article proposes a zero-trust access management
framework for the healthcare information system. The article also conducted a
case study on misuse cases to verify the framework’s viability.
Misuse cases in health care are defined as circumstances that lead to a wrong
medical decision. The decision may lead to prescribing the wrong drug [1, 2],
issuing the wrong report, or a false diagnosis. The misuse is very critical as
it may be caused by normal users, not just by fraud. In healthcare 90% of
vulnerabilities are from misuse cases or human errors. This is difficult to
detect as it is caused by authorized and authenticated users. In the era of
generative AI assistance, which could generate biased, discriminated, or even
wrong medical reports [3]. The misuse cases are caused either by human or AI-
assistant systems. The proposed framework is designed to make a scoring system
for any type of user, data or device.

Controlling access to devices and their users (either human or AI) and
associated data in healthcare systems is a major challenge for any service
provider. While promoting the idea of smart hospitals and telehealth, it is
required to look deeply into the existing regulation and access control
systems to be more valid in the context of using technologies like internet of
things (IoT) devices, cloud [4], AI [5, 6], blockchain [7, 8], quantum
computing [9, 10] and 5G networks [11]. There are different types of medical
devices that are used within the distributed or cloud-based healthcare
information environment. Examples of these devices are patient monitoring
devices, handheld and portable devices, telehealth consulting, medical imaging
systems, robotics, and virtual reality.

The main challenges facing the cloud-based healthcare infrastructure are
managing access to these devices and guaranteeing that the received data is
secure, clean, and clinically valid. The stressful environment and complex
technology require serious attention and advanced skills to operate such
systems. At the same time, the devices and the data should be monitored in
real-time to intercept any abnormalities in data or wrong reports sent by
healthcare practitioners. Such a system should control users, data and output.

Constraints: The healthcare industry is subject to strict regulations
regarding the use of patient information. In the United States, the Health
Insurance Portability and Accountability Act (HIPAA) governs patient
information compliance. Similarly, in Canada, Bill (C-27) regulates the
healthcare information system, and Health Canada also plays a role. Bill
(C-27) is a new law that replaces The Personal Information Protection and
Electronic Document Act (PIPEDA) and has enacted three regulations: the
Consumer Privacy Protection Act (CPPA), the Personal Information and Data
Protection Tribunal Act (PIDPTA), and the Artificial Intelligence and Data Act
(AIDA). In Europe, compliance with the General Data Protection Regulation
(GDPR) regulates the sharing of information in healthcare.

Proposed solution: To adapt to the new advancement in technology and strict
compliance, the paper proposes a zero-trust context-aware access control
framework for medical IoT devices that can manage the patient information
system within the complex structure of healthcare systems. The framework
proposes a set of practices, policies and attributes to enhance and manage the
security of access control systems for any healthcare infrastructure. The
framework mainly focuses on preventing misuse cases in the healthcare
industry. These cases are complex and difficult to detect as they are sent by
authorized and authenticated users. The proposed context-aware system can
alleviate the user’s errors by analyzing the complex metadata of the user,
device and output. The proposed context-aware framework ensures that the data
is relevant, consistent, authenticated and only sent by authorized users to
the designated destination at the end point device or user.

The contributions of this article are as follows:

  * •

Propose zero trust context-aware access management framework that relies on
the user ($x$), hardware ($y$) and output data ($z$), Sec. 3.

  * •

Design critical trust assessments based on cloud-native micro-services of
authentication, authorization, encryption and logging, Sec. 3.3.

  * •

Implement bond trust scoring assessment based on the analysis of syntactic and
semantic relationship between $x$, $y$ and $z$. Bond trust is used to build a
chain of trust between different entities in healthcare information systems.
It is derived using a pre-trained word2vec machine learning model, Sec. 3.3.

  * •

Construct hierarchical encoding for decision-making of the framework to grant
a complex final decision that considers regulatory compliance, access
constraints, access level and access operations, Sec. 3.4.

  * •

Conduct a study to evalaute the framework to assess the validity of this
framework on preventing misuse cases in healthcare industry. Sec. 4.

The rest of the article is organized as follows. Sec. 2 provides a background
of the current access control work. Sec. 3 explain the proposed framework in
detail. Sec. 4 report and discuss the experiment results. Sec. 5 concludes the
paper.

##  2 Background and current access control system for IoT devices in
healthcare

While the traditional access control systems are sufficient within the local
hospital environment, they have limited security or functionality outside the
perimeter of the local healthcare infrastructure. The emerging need for
distributed IoT devices that require internet connections and advanced server
or cloud infrastructure to store, compute and manage data interoperability
makes it challenging, especially in the era of AI, which requires a new access
control policy. The existing healthcare information systems rely on the
HL7FHIR standards [12] to define the communication and security access control
system in healthcare. There are three main subsystems within the HL7FHIR:

  1. 1.

Authentication: To verify the user.

  2. 2.

Access Control Engine: To decide which FHIR controls are allowed for the user
using the CRUD method (Create, Read, Update, Delete).

  3. 3.

Audit log: to record the actions and any suspicious system intrusion.

At the organizational level, the access control system has three main common
types within the health information system:

  * •

RBAC: Role-based access control [13], [14].

  * •

ABAC: Attribute-based access control [15, 16].

  * •

CML: Modern cloud-based machine learning access control [17, 18, 19].

The RBAC and ABAC are the standard access control systems in healthcare. They
are used widely in the traditional healthcare infrastructure setup for
managing access control within the hospital perimeter. The RBAC manages the
access based on the user role and grants permission based on the CRUD or HTTP
method. RBAC is complex and considers different factors like users (operator,
patient), roles, permissions, resources objects and context of the data access
[20, 12]. Please refer to Table 6 in Appendix A for more information on the
Role-based access system factors. The limitation of a rule-based access
management system is that it is time-consuming and requires a lot of manual
work to adjust rules and policies, which makes it less effective in real-time
access management that has too many factors in a complex cloud-based
environment.

The ABAC [21, 22] grants the user permission to access the system resources or
objects based on predefined policies and conditions that are characterized by
specific data attributes. For example, to adhere to compliance regulations,
the patient identification information can not be accessed without having the
patient consent attribute to process the data. The ABAC has a few challenges;
it is difficult to scale, which limits its use in the cloud ecosystem. In
addition, it needs a considerable amount of time and resources, which makes it
inflexible and inefficient in a dynamic and modern globally distributed
healthcare system.

To access health information in a traditional access engine, the user
typically sends a request to the server through the REST API gateway. The
server then sends a request for the REST API to verify the user information to
grant the required CRUD operations based on the predefined rules and policies.
Authenticating IoT devices also is challenging and requires special
techniques. For example, the Physical Unclonable Function (PUF) is used to
authenticate the hardware for the telehealth distributed devices [23].

The modern Cloud-based ML access control systems rely mainly on the zero trust
principle that analyzes everything in the network and does not grant trust to
any entity, either a user or device, for data access without passing a set of
conditions that are defined by the organization policy. However, the main
challenge is to identify what attributes or data context that will be
considered in the policy without compromising the quality of the provided
service. Mitigating the risk within the network is also essential to evaluate
the access decision of the users [24].

Fig. 1 depicts the main sources of data for IoT devices in the cloud-based
healthcare environment. Picture Archiving Communication System (PACS) stores
images in Digital Imaging and Communications in Medicine (DICOM) format.
Electronic Health Records (EHR) keep the patient records using High-Level
Seven (HL7) and Fast Healthcare Interoperability Resources (FHIR) standards.
Patient monitoring data is also sent in real-time for data analysis, doctor
observations, and data from different distributed IoT devices. These data
sources are the essential backbone for the health information system data
sources. Data ingestion and processing in Digital health applications can be
handled using AI tools like transformer [25]. The transformer is a state-of-
the-art AI algorithm that can extract the relationship between different
healthcare components using an attention mechanism.

Figure 1: Illustration of the main data sources of IoT devices in Cloud-based
telehealth ecosystem.

##  3 Method

###  3.1 Overview of the proposed zero trust framework for access management

The architecture design for the proposed context-aware access management
frameworks is depicted in Fig. 2. The proposed access control system considers
the zero-trust context-aware system that manages and analyses the data journey
from the user of medical IoT device endpoints to the cloud resources
destination. The proposed framework is classified into three main layers, as
listed below:

  * •

Cloud input sources: Is the front-end gateway for the main input source from
users, devices metadata and the context of data output either in the storage
of real-time streaming.

  * •

Cloud decision engine: Build a chain of trust for each component based on the
trust scores. There are two scores: critical trust ($CT$) and bond trust
($BT$). Then, the engine encodes the context attributes for further analysis
at a hierarchical level. In the end, it grants the final access decision,
operations and constraints based on the analysis.

  * •

Cloud resources: Contains the cloud computing and storage resources that are
used to process and store the metadata in the healthcare database.

Figure 2: Representative of the proposed access control functional diagram
within the healthcare cloud-AI ecosystem.

The following subsections explain the components of the proposed framework in
detail.

###  3.2 Zero trust cloud input sources

The proposed system harnesses the zero trust context-aware system to manage
access from the cloud input sources. The zero trust principle is based on
utilizing all available data points for access management, including user
identity, location, device health, services, workload, or data classification.

There are three main components for the context-aware cycle that consider the
context of the zero-trust five elements. Fig. 3 depicts the three components
of the trust cycle. Who is the user, which device is used, and what is the
output?

Figure 3: Trust Cycle of the proposed access control framework.

The trust cycle has five elements that are pillars of the proposed zero-trust
principle.

  1. 1.

User (Identity)

  2. 2.

IoT device (Hardware)

  3. 3.

Network (Device connection)

  4. 4.

Application Workload (Output patterns and scale)

  5. 5.

Data (Output transaction context)

Where the identity relates to the user, the IoT device and the network related
to the hardware component. The application workload and transaction context
relate to the output component.

###  3.3  Maintain chain of trust and evaluate trust score

While building trust to decide what type of access each component will have is
essential, guaranteeing that there are no human errors or malicious attacks is
challenging. To address this issue, our access control management protocol
will continuously evaluate the trust score and build a chain of trust. The
chain of trust is important to decide what level of access can be granted and
to deny access if the connection is below the threshold of an acceptable trust
score. Fig. 4 illustrates the chain of trust within the cloud ecosystem.

The proposed framework constructs two assessment scoring criteria to manage
the access of distributed medical devices. First is the critical trust ($CT$),
which relies on cloud-native microservices. Second is the bond trust ($BT$),
which is a proposed scoring schema to manage access control, as explained
below. $BT$ uses machine learning pre-trained models to analyze the semantic
and syntactic attributes from the trusted and authorized change of zero trust
pillars 3, that are related to uses, devices and data.

Figure 4: Proposed framework of a continuous chain of trust based on the
accumulated trust score of the zero trust of each access management component.

Critical Trust ($CT$): Is the first assessment score that is used to grant
initial access to the cloud ecosystem but not for direct connection to other
resources. $CT$ is evaluated using cloud-based micro-services. There are four
main micro-services attributes for the critical trust score. Authentication,
authorization, logging and encryption are all attributes that are used to
obtain a value for $CT$ as per Eq. (1).

Each micro-service attribute is given a logical value, 1 or 0. Then, these
micro-services logical values are multiplied by a scoring factor ($S_{i}$)
based on its importance that can be set by the system admin. The cloud
decision engine grants access status to allow for trusted authority, verify if
more information is needed, and deny for untrusted access requests.

$CT=S_{1}\times A_{1}+S_{2}\times A_{2}+S_{3}\times A_{3}+S_{4}\times A_{4}$
(1)

where $A_{1}$ is authentication and its scoring factor is $S_{1}$, $A_{2}$ is
the authorization and its scoring factor is $S_{2}$, $A_{3}$ is the encryption
and its scoring factor is $S_{3}$, $A_{4}$ is the logging and its scoring
factor is $S_{4}$. Table 1 provides an example of critical trust score
evaluation using different scoring factors and micro-services logical values.

Table 1: Examples of critical trust score assessment.  ID |  $A_{1}$ |  $S_{1}$ |  $A_{2}$ |  $S_{2}$ |  $A_{3}$ |  $S_{3}$ |  $A_{4}$ |  $S_{4}$ |  Critical trust score |  Access status
---|---|---|---|---|---|---|---|---|---|---
D1 |  1 |  0.3 |  1 |  0.4 |  1 |  0.2 |  1 |  0.1 |  0.9999 |  Allow
D2 |  1 |  0.3 |  0 |  0.4 |  1 |  0.2 |  1 |  0.1 |  0.6 |  Verify
D3 |  0 |  0.3 |  0 |  0.4 |  0 |  0.2 |  0 |  0.1 |  0 |  Deny

Bond Trust ($BT$): Once the transaction is passed the critical trust
assessment, the bond trust will evaluate the relationship to other resources
to build a chain of trust to the only authorized and highly trusted actors to
make sure that the data or resources are accessed by designated people based
on the organization policy or rules. Calculating Bond Trust is more complex
and depends on different aspects. $BT$ has two main assessment criteria. First
is $BT_{A}$, which assesses the semantic relationship between each individual
attribute stored in the health care information system. Second is $BT_{B}$,
which assesses the syntactic relationship between the set of candidates in a
generated health report. The reason for using these two measures as the first
one is that it is essential that each attribute has meaningful meaning and is
related to similar attributes compared to the pre-trained ones. The second one
is essential to guarantee that the attributes in the generated report are in
the context of the patient’s history to ensure that the report is highly
likely related to the same patient and, hence, is not diagnosed falsely with
the wrong case.

The proposed assessment of $BT_{A}$ uses Attribute2Vec representation that is
based on the pre-trained word2vec model [26], [27]. The Attribute2Vec maps the
attributes and their synonyms words that have the same context from the user
($x$), hardware ($y$), and output ($z$) attributes stored in their electronic
health records. The skip-gram methodology [28] is used to derive the
attributes with the same context, and we suggest in this framework using the
first three words with the highest context probability. The advantage of using
this assessment technique is to generalize the model by accepting a wide
variety of attribute descriptions in a global context. word2vec is valid for
different languages and dialects. For example, it has been used by Altibbi.com
[29] to train 1.5 Million medical consultation questions in the Arabic
language. We recommend using a matching engine on the Vertex AI platform at
Google Cloud to make sure the word embedding and vector similarity matching
process is efficient and reliable. Fig. 5 depicts the process of assessing
bond trust.

Figure 5: Semantic trust assessment using attribute2vec based on word2vec
model. Where $BT_{A(1)}$, $BT_{A(2)}$, and $BT_{A(3)}$ are the set of bond
trusts between the three input sources $x$,$y$, and $z$. $BT$ is the final
bond trust score.

Cosine distance is used in Eq. (2) to predict the similarity probability of
the context of attributes of $x$, $y$, and $z$.

$\textit{Similarity
(A,B)}=\cos(\theta)=\dfrac{\vec{A}\cdot\vec{B}}{\left\|\vec{A}\right\|\left\|\vec{B}\right\|}$
(2)

where $\vec{A}\cdot\vec{B}=\sum_{i=1}^{N}(A_{i}\times B_{i})$ is the dot
product between two vector attributes $\vec{A}$ and $\vec{B}$. At the same
time, $\left\|\vec{A}\right\|=\sqrt{\sum_{i=1}^{N}(A_{i})^{2}}$,
$\left\|\vec{B}\right\|=\sqrt{\sum_{i=1}^{N}(B_{i})^{2}}$ are the L2-norms of
the attributes $\vec{A}$, $\vec{B}$ respectively. While $\theta$ is the angle
between the two vectors.

The highest probability attribute vectors between $x$, $y$, and $z$ will be
used to derive the bond or semantic mutual relationship in three Bond Trust
scores sets $BT_{A(1)}$, $BT_{A(2)}$ and $BT_{A(3)}$ for the relationship
between $xy$, $xz$ and $yz$. Where $BT_{A(i)}$, the bond trust sets are
derived using two inputs:

A. Cosine similarity logical evaluation: Algorithm 1 is used to assign a
logical value for the cosine similarity between two attributes. There is a
given value of either one or zero based on the relationship of the attributes
$x$,$y$ and $z$. The value is assigned based on the threshold of the angle
$\theta$ between the two attributes. Eq. (2) is used to derive $\theta$ using
cosine similarity between the attribute vector product for the given ($i$)
index or position for similar context attributes. The algorithm produces a set
of three logical values $Sim_{A}(\vec{x}_{i},\vec{y}_{i})$,
$Sim_{B}(\vec{x}_{i},\vec{z}_{i})$, $Sim_{C}(\vec{y}_{i},\vec{z}_{i})$, for
each given index($i$).

Algorithm 1 An algorithm for proposed cosine similarity logical evaluation
process

Input: User ($x$), IoT hardware ($y$) , IoT output data ($z$), Angle Threshold
($Th_{\theta}$)

1:if ${\theta}_{xy}\geq Th_{\theta}$ then

2: $Sim_{A}(\vec{x}_{i},\vec{y}_{i})=1$

3:else if ${\theta}_{xy}<Th_{\theta}$ then

4: $Sim_{A}(\vec{x}_{i},\vec{y}_{i})=0$

5:end if

6:if ${\theta}_{xz}\geq Th_{\theta}$ then

7: $Sim_{B}(\vec{x}_{i},\vec{z}_{i})=1$

8:else if ${\theta}_{xy}<Th_{\theta}$ then

9: $Sim_{B}(\vec{x}_{i},\vec{z}_{i})=0$

10:end if

11:if ${\theta}_{yz}\geq Th_{\theta}$ then

12: $Sim_{C}(\vec{y}_{i},\vec{z}_{i})=1$

13:else if ${\theta}_{yz}<Th_{\theta}$ then

14: $Sim_{C}(\vec{y}_{i},\vec{z}_{i})=0$

15:end if

16:Output: $Sim_{A}(\vec{x}_{i},\vec{y}_{i})$,
$Sim_{B}(\vec{x}_{i},\vec{z}_{i})$, $Sim_{C}(\vec{y}_{i},\vec{z}_{i})$

B. Weight: The weight is calculated using the GloVe model [30] of word
embedding to consider the co-occurrence of the attributes in a global
representation context of the healthcare database. The weight is based on the
conditional probability of attribute occurrence or importance as in Eq. (3).

$w_{i}={\frac{P_{BA}}{P_{B}}}$ (3)

where $w_{i}$ is the probability of word B occurrence in the context of the
word A of a given ($i$) index of two semantic or syntactically similar
attributes.

The three scaler values of $BT_{A(1)}$, $BT_{A(2)}$ and $BT_{A(3)}$ are stored
in $BT_{A}$ as shown in Eq. (4). Where $BT_{A}$ is a $1\times 3$ vector.

$BT_{A}=[BT_{A(1)},BT_{A(2)},BT_{A(3)}]$ (4)

where $BT_{1}$ is the relationship score between the user ($x$) and hardware
($y$) and is derived using Eq. (5). $BT_{2}$ is the relationship score between
the user ($x$) and output ($z$) and is derived using Eq. (6). $BT_{3}$ is the
relationship score between the output ($z$) and hardware ($y$) and is derived
using Eq. (7).

$BT_{A(1)}=\sum_{i=1}^{N}{(w_{i})_{xy}\cdot Sim_{A}(\vec{x}_{i},\vec{y}_{i})}$
(5)

$BT_{A(2)}=\sum_{i=1}^{N}{(w_{i})_{xz}\cdot Sim_{B}(\vec{x}_{i},\vec{z}_{i})}$
(6)

$BT_{A(3)}=\sum_{i=1}^{N}{(w_{i})_{yz}\cdot Sim_{C}(\vec{y}_{i},\vec{z}_{i})}$
(7)

where $w_{i}$ is a scalar weight that is used to scale the bond score for each
attribute based on the importance of the feature at given ($i$) and derived by
Eq. (3). ${N}$ is the sequence number of attributes that are numbered based on
the probability of their context relationship. Only each similar class
attribute of user, devices and output are multiplied by each other, and if
they belong to the same category, the algorithm gives them either a 0 or 1
similarity score and then multiplies them by the scalar weight for that
attribute. The step is then repeated for all attributes. The final
multiplication is aggregated to have a final scalar number that resembles the
combined similarity score for $BT_{A(i)}$.

$BT_{A(i)}$ vector is normalized in Eq. (8) using the $SoftMax$ function. The
normalization process produces a new vector $BTN$ of a $1\times 3$ dimension.

$BTN_{i}=\textit{SoftMax}(BT_{A(i)})=\frac{\exp(BT_{A(i)})}{\sum_{j}\exp(BT_{A(j)})}$
(8)

The result is stored in Eq. (9) and has three scalar values that are between
zero and one.

$BTN_{i}=[BTN_{1},BTN_{2},BTN_{3}]$ (9)

The first part of the bond score is calculated in Eq. (10) by aggregating the
three normalized scores $BTN_{1}$, $BTN_{2}$ and $BTN_{3}$.

$BT_{A}=BTN_{1}+BTN_{2}+BTN_{3}$ (10)

where $BT_{A}$ is between zero and one. Zero is for non-matched attributes,
and one is for the highest attribute similarity match. Any number between zero
and one requires an additional trust verification and reassessment.

At the same time, $BT_{B}$ is used to evaluate the syntactic performance of
the candidate report generated from the stored data in the healthcare
information system. $BT_{B}$ is inspired by the $BLEU$ score [31], which was
originally designed by IBM for machine translation scoring evaluation as shown
in Eq. (11).

$BT_{B}=\min(1,exp(1-\frac{reference-length}{output-
length}))(\Pi^{n}_{i=1}precision_{i})^{1/n}.$ (11)

where $BT_{B}$ has two parts. First is the brevity penalty that compensates
for the length of a short generated report. Second, the precision for n-gram
candidates. The $n$ refers to the number of candidates used to evaluate the
score. $n$ typically is 4 and can be increased to include more restrictions
for identifying the misuse cases. In the case of $n=4$, the $BLEU$ score needs
the candidate report to match the reference template by at least four
attributes.

In the case of no history, the score is zero, and it becomes more meaningful
and has more weight in the case of existing patient history.

The final bond trust normalizes the summation of $BT_{A}$ and $BT_{B}$ to keep
the value between zero and 1 ad in Eq. (12).

$BT=\frac{BT_{A}+BT_{B}}{2}$ (12)

###  3.4 Access control decision engine encoding and hierarchy

There are two main stages for the decision engine encoding and hierarchy.
These stages are essential to make sure that the final decision follows a
chronological and logical flow of different conditions. While the encoding
Fig. 6, depicts the two stages of encoding and hierarchy process for access
control management.

Stage one: The decision engine performs the initial critical check for the end
point device or user request access from the server. The critical check is
essential to guarantee that the endpoint components have passed the regulatory
compliance and critical trust score threshold, Table. 1. An example of one of
the main regulatory compliance that needs to be considered is the HIPAA, which
lists 18 patient information identifiers [32] that are restricted from being
shared without having consent from patients and meet all security guidelines
within the healthcare information system as shown in Table 7.

Stage two: The decision engine encodes the attributes from devices, output,
users and critical trust in a 32-digit hexadecimal array. The 32-digit array
is then analyzed to make the final decision. The final decision is also
encoded to resemble the access level, operations, access resources and
constraints, see Sec. 3.5.

Figure 6: Representative of the access control engine decision hierarchy and
the encoding.

Fig. 7 illustrates an example of the encoding schema for the proposed three
zero-trust components, user, device and output, based on different attributes.
Each component has a 10-digit hexadecimal value and a 2-digit value for each
one of the five attributes. The importance of these attributes is to ensure
that the access request belongs to the designated group, has a pre-defined
access level and type, and passes the bond trust.

Figure 7:  Proposed access control encoding. (A) User Encoding. (B) Device
Encoding. (C) Output encoding. PC is the patient consent.

###  3.5 Final decision and access operations

The final decision has four main criteria and information, as listed below.
Table. 2 depicts the final decision encoding information using hexadecimal
digits.

  * •

Access level: Decide the access level for each transaction.

  * •

Access resources: Decide which storage and computation resources will be used.

  * •

Access constraints : Decide what the access constraints are, such as duration,
location, number of access trials, and size of data transferred.

  * •

Access operations: Grant access based on CRUD or HTTP method.

Table 2: Final decision encoding.  F |  Decision |  Hex |  Encoding Description
---|---|---|---
F1 |  Access Level |  2 digits |  To specify the five access levels. Ex. 10 for access level L0.
F2 |  Access resources |  6 digits |  The first three digits are for compute resources and the rest are for storage resources metadata.
F3 |  Access constraints |  16 digits |  8 digits for time, and the other eight digits for other constraints. Ex. 6421EC5F for 2023Y,03M,27D,21h,19mm,59ss.
F4 |  Access operations |  1 digit |  ex. F, in hexadecimal, for admin access of all operations

Algorithm 2 shows the logical process of the proposed framework. The framework
has three inputs $x$, $y$ and $z$. The initial step requires passing the
threshold for $CT$ and $BT$ that is specified by the system admin. Typically
$CT\geq 99.99\%$ , $BT\geq 0.7$, where each attribute in $BT_{i}\geq\theta$.
If the score of $CT$ and $BT$ was zero, the access was denied, and any value
between zero and threshold, the access should be verified again within a given
time interval. The final access decision will be granted based on the trust
scores assessment.

Algorithm 2 Proposed access management framework logical process

Input: User ($x$), IoT hardware ($y$) , IoT output data ($z$)
Trust assessment: Critical trust ($CT$), Bond trust ($BT$), Trust threshold
($Th$)

1:if $CT=0$ , $BT=0$ then

2: Deny access

3:end if

4:while $Th\neq 0$ do

5: if $CT\geq Th$ , $BT\geq Th$ then

6: Initially accepts access

7: else if $CT<Th$ , $BT<Th$ then

8: Verify access again

9: end if

10:Output: Grant final access decision

11:end while

##  4 Experiment and results

###  4.1 Dataset information

The dataset used in this experiment contains a synthetically generated set of
attributes for users, medical IoT devices and data. The generated data is
synthesized using Synthea [33]. The synthetic dataset is used to fine-tune the
word2vec model to enhance the result within a healthcare information system.
Fig. 8 shows some examples of the generated dataset attributes of users,
devices and data that are used to prevent misuse cases.

Figure 8:  Example of selected attributes from the generated data using
Synthea and fine-tuned the word2vec pre-trained model.

The synthetic dataset is not limited to only a small subset of attributes.
These attributes are extracted from large language models, and they include
all attributes that are related to the healthcare information system for the
main three categories user, device, or data. Examples of some of these
categories are listed in Table. 8.

In order to evaluate the syntactic information, we generated a sample of
different patient reports based on a predefined template from the same set of
attributes mentioned before. The generated templates generate all possible
syntactic and semantic similar reports that may be related to the patient
based on the medical history. Fig. 9 depicts the template used to generate the
final report that includes information about users, devices and data.

Figure 9:  Arbitrary example of generated text prompt from patient history
record. The mentioned names are arbitrary examples and do not refer to any
true identity.

###  4.2 Experiment results and discussion

The ablation study is examined to evaluate the accuracy of identifying the
misuse cases using the proposed model by examining the relationship between
different attributes based on the critical and bond trust scoring. The study
was conducted using 17625 attributes for users, medical IoT devices, and data
output categories. The study shows that the F1-score is $93.5\%$, which means
that the proposed methodology is valid for identifying the relationship
between different attributes within the healthcare information system and
alleviating any misuse cases that may produce false medical reports. Fig. 10
depicts the confusion matrix of the experiment result.

Figure 10:  Confusion matrix for the ablation study on the accuracy of
detecting misuse cases by identifying the relationship between selected
attributes. TP is true positive; FP is false positive; FN is false negative;
TN is true negative.

Evaluating the final results has different criteria for semantic and syntactic
information. Semantic information is used to evaluate the relationship of each
word in the context of medical-related data. At the same time, syntactic
information analysis is used to evaluate the corpus context of the newly
generated report and compare it with the stored data in a healthcare
information system. Table 3 lists some examples of the evaluation of the
$BT_{A}$ to extract semantic relationships from the healthcare information
system for different medical specialty classes.

Table 3: The precision, recall, and f1-score for evaluating $BT_{A}$ on a selected variety of speciality cases.  Speciality Class |  Precision |  Recall |  F1-score
---|---|---|---
Radiology |  0.880 |  0.880 |  0.880
Gynecology |  0.773 |  0.840 |  0.805
Oncology |  0.793 |  0.772 |  0.782
Dermatology |  0.712 |  0.740 |  0.726
Cardiology |  0.833 |  0.871 |  0.851
Urology |  0.765 |  0.724 |  0.744
Emergency |  0.865 |  0.834 |  0.849
Dentistry |  0.79 |  0.77 |  0.779
Psychology |  0.766 |  0.784 |  0.774

Table. 4 shows the effect of syntactic analysis using different measures on
the final decision. As shown in the table, the 1-gram measure of the accuracy
of detecting one word compared to the context of reference length from the
stored data in the healthcare system. While it has high precision, it is not
accurate for making decisions as it does not account for the relationship with
other attributes. The decision confidence increases gradually with reference
to the n-gram rank as it has a more meaningful meaning.
The BLEU score is good for judging a corpus of attributes but performs badly
on a single entry. In the case of syntactic analysis, it is more efficient to
score the generated reports. However, it is not efficient for judging semantic
information or detecting grammatical error sentences.

The proposed method got the best results as it accounts for semantic and
syntactic information. The decision engine in the cloud generates different
reports from the stored data that account for different synonyms, words or
attributes that are related to the stored data. It also can fix any
grammatical errors in the entry and suggest an attribute within the same
context. This gives the method a generalized capability to assess any new
report or data entry within the healthcare information system through
distributed users, devices and sorted data. At the same time, the proposed
method accounts for the security measure that requires authentication,
authorization, encryption and logging. Table 4 compares the confidence score
of the proposed method with other scoring metrics that are used for syntactic
analysis.

Table 4: Comparison of proposed scoring method and other metrics of syntactic analysis.  Metric |  Decision confidence score
---|---
1-gram |  26%
2-gram |  33%
3-gram |  47%
4-gram |  66%
BLEU |  71%
Proposed method |  89%

The proposed framework focuses on the cloud-AI access control system by
managing the access to the cloud resources for users, devices, and data. This
is done by implementing a zero-trust context-aware system that analyzes the
data for each transaction and always for the uses of the users, devices,
network, workload and data. The framework considers the information security
model that has three pillars of data confidentiality availability. Regulatory
compliance is also part of context-aware access control. HIPAA is the most
important compliance that identifies protected health information data. The
protected data can not be used without following a series of security and
privacy protection guidelines like patient consent, disclosure agreement, de-
identifications, data encryption and a well-managed access control system.

The framework also takes advantage of cloud-native microservices to implement
critical trust assessment criteria. To build a chain of trust between
different attributes for each component, the framework proposes bond trust
evaluation that is inspired by the large language models.

Table. 5 shows a sample of results for access management decisions based on
the evaluation of the critical trust ($CT$) and bond trust ($BT$) assessments.

Table 5: Example of access management decision based on scoring evaluation.  N(Samples) |  $CT$ (avg.) |  $BT$ (avg.) |  Decision
---|---|---|---
402 |  0 |  0 |  Decline
267 |  0.99 |  0 |  Decline
224 |  0.99 |  0.5 |  Verify
259 |  0.99 |  0.9 |  Accept
110 |  0.99 |  0.83 |  Accept
479 |  0.99 |  0.79 |  Accept

While the zero trust context-aware system is robust against different
situations, there are different challenges and limitations to implementing it
in the healthcare industry, as follows:

  * •

Data Privacy and Security: ML acts as a backbone of the zero trust access
control system, which requires being trained on a considerably large dataset,
the size required be in millions or even billions of parameters to get
efficient results. Obtaining sensitive and accurate data is challenging due to
privacy concerns for health information regulatory compliance, which may limit
the accuracy of the system.

  * •

Complexity: The complex healthcare IT infrastructure makes it difficult to
implement and manage a zero-trust context-aware access control system. These
systems need to be able to integrate with existing systems and applications,
and they need to be able to handle the large volume of data that is generated
in healthcare settings.

  * •

Cost: Implementing a zero trust access control system requires an enormous
investment in backend infrastructure. The costs of implementing and
maintaining these systems need to be balanced against the potential benefits,
such as improved data security and reduced risk of data breaches, compared to
the cost of investment.

  * •

Skills: Zero trust principles rely on too many factors. These factors should
be aligned with the current and most advanced technology, which requires
highly skilled professionals who are always in demand due to the shortage of
these skills in most employees.

##  5 Conclusions

The access control system is one of the essential components of any
information system that overcomes the three main challenges of data
interoperability, confidentiality, availability and integrity. The proposed
framework handled the three main challenges by proposing dynamic zero trust-
based context-aware access management that analyzes the data from users,
devices and output to decide the level of access, constraints, resources and
operations. The results show that the combination of zero trust using cloud-
based microservices and bond trust using semantic and syntactic analysis is
able to detect misuse cases by a high confidence score compared to other
scoring algorithms. The proposed framework also considers security and
regulatory compliance in addition to semantic or syntactic information
attribute search. For future work, other technical elements should be
considered in the access control system design. Examples of some of these
elements are quantum computing, post-quantum encryption and blockchain
technology.

Abbreviations:

AI: | Artificial intelligence
---|---
AIDA: | Artificial intelligence and data act
ABC: | Attribute-based access control
BT: | Bond trust
CT: | Critical trust
CPPA: | Consumer privacy protection act
CML: | Cloud and machine learning-based access control
CRUD: | Create, read, update, delete
DDoS: | Distributed denial of service attacks
GDPR: | General data protection regulation
IoT: | Internet of things
ML: | Machine learning
PIPEDA: | Personal information protection and electronic document act
PIDPTA: | Personal information and data protection tribunal act
RBC: | Role-based access control
SQL: | Structured query language

##  Appendix A Access control system information

###  A.1  Role-based access control system important factors

Table 6: Examples of Role-based access control system data sources information. Information source |  Example of data source information factors
---|---
Client or operator |  User id, role, department, level of access, geographic location
Patient |  Patient ID, clinical condition, department, family doctor name, patient consent policy
Resources |  Confidentiality, sensitivity, type of data, date ranges covered by the data, author of the data
Data context |  System identity, transaction time, the expiration time of token data, the scope and purpose of the token, security of transaction

###  A.2  HIPPA 18 Restricted Patient Identifiers

Table 7: HIPAA 18 patient protected identifiers [32].  Iden. |  Description |  Iden. |  Description
---|---|---|---
1 |  Names |  10 |  IP address
2 |  SN (Social security number) |  11 |  Medical records number
3 |  Geographic locations smaller than states |  12 |  Biometrics identifiers
4 |  Telephone numbers |  13 |  Health plan beneficiary numbers
5 |  Fax numbers |  14 |  Full face photographs
6 |  Devices IDs and serial numbers |  15 |  Account numbers
7 |  Email address |  16 |  Any other unique identifying numbers
8 |  Web URLs |  17 |  Certificate; license numbers
9 |  Vehicle identifiers (eg. license plate) |  18 |  All element of dates (Except years)

###  A.3 Data category example

Table 8: Example of some attributes from the generated dataset categories.  Attribute example |  Category
---|---
Position |  User
Department |  User
Speciality |  User
ID |  User
Insurance number |  User
User access level |  User
User consent |  User
Password |  User
Manager ID |  User
MAC address |  Device
IP address |  Device
Device model |  Device
Device type |  Device
Device location |  Device
Device manufacture |  Device
Data category |  Data
Data encryption |  Data
Data storage location |  Data
Storage type (Ex. Container, SSD, VM…) |  Data
Data sensitivity level |  Data
Data compliance |  Data

## References

  * [1] G. Cousins, L. Durand, A. O’Kane, J. Tierney, R. Maguire, S. Stokes, D. O’Reilly, E. Arensman, K. E. Bennett, M. O. Vázquez, et al., Prescription drugs with potential for misuse: protocol for a multi-indicator analysis of supply, detection and the associated health burden in ireland between 2010 and 2020, BMJ open 13 (3) (2023) e069665.
  * [2] A. R. Islam, K. M. Khan, A. Scarbrough, M. J. Zimpfer, N. Makkena, A. Omogunwa, S. I. Ahamed, An artificial intelligence–based smartphone app for assessing the risk of opioid misuse in working populations using synthetic data: Pilot development study, JMIR Formative Research 7 (1) (2023) e45434.
  * [3] V. Volovici, N. L. Syn, A. Ercole, J. J. Zhao, N. Liu, Steps to avoid overuse and misuse of machine learning in clinical research, Nature Medicine 28 (10) (2022) 1996–1999.
  * [4] A. A. Nancy, D. Ravindran, P. D. Raj Vincent, K. Srinivasan, D. Gutierrez Reina, Iot-cloud-based smart healthcare monitoring system for heart disease prediction via deep learning, Electronics 11 (15) (2022) 2292.
  * [5] M. Valizadeh, N. Parde, The ai doctor is in: A survey of task-oriented dialogue systems for healthcare applications, in: Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 2022, pp. 6638–6660.
  * [6] H. W. Loh, C. P. Ooi, S. Seoni, P. D. Barua, F. Molinari, U. R. Acharya, Application of explainable artificial intelligence for healthcare: A systematic review of the last decade (2011–2022), Computer Methods and Programs in Biomedicine 226 (2022) 107161.  doi:10.1016/j.cmpb.2022.107161.
URL https://www.sciencedirect.com/science/article/pii/S0169260722005429

  * [7] S. Chauhan, H. K. S. Tanwar, Application of blockchain technology in healthcare: A systematic review, in: 2022 International Conference on Applied Artificial Intelligence and Computing (ICAAIC), IEEE, 2022.  doi:10.1109/icaaic53929.2022.9792750.
URL https://doi.org/10.1109%2Ficaaic53929.2022.9792750

  * [8] A. Lakhan, M. A. Mohammed, J. Nedoma, R. Martinek, P. Tiwari, A. Vidyarthi, A. Alkhayyat, W. Wang, Federated-learning based privacy preservation and fraud-enabled blockchain iomt system for healthcare, IEEE Journal of Biomedical and Health Informatics (2022).
  * [9] R. U. Rasool, H. F. Ahmad, W. Rafique, A. Qayyum, J. Qadir, Quantum computing for healthcare: A review (2022).
  * [10] A. Kumar, B. Bhushan, S. Shriti, P. Nand, Quantum computing for health care: A review on implementation trends and recent advances, Multimedia Technologies in the Internet of Things Environment, Volume 3 (2022) 23–40.
  * [11] B. Chen, S. Qiao, J. Zhao, D. Liu, X. Shi, M. Lyu, H. Chen, H. Lu, Y. Zhai, A security awareness and protection system for 5g smart healthcare based on zero-trust architecture, IEEE Internet of Things Journal 8 (13) (2020) 10248–10263.
  * [12] HL7FHIR, 6.1.0 fhir security, last accessed 16 Feb 2023 (2023).
URL https://build.fhir.org/security.html

  * [13] S. Zhang, S. Yang, G. Zhu, E. Luo, J. Zhang, D. Xiang, A fine-grained access control scheme for electronic health records based on roles and attributes, in: Ubiquitous Security: First International Conference, UbiSec 2021, Guangzhou, China, December 28–31, 2021, Revised Selected Papers, Springer, 2022, pp. 25–37.
  * [14] M. Rashid, S. A. Parah, A. R. Wani, S. K. Gupta, Securing e-health iot data on cloud systems using novel extended role based access control model, Internet of Things (IoT) Concepts and Applications (2020) 473–489.
  * [15] S. Khan, W. Iqbal, A. Waheed, G. Mehmood, S. Khan, M. Zareei, R. R. Biswal, An efficient and secure revocation-enabled attribute-based access control for ehealth in smart society, Sensors 22 (1) (2022) 336.
  * [16] M. W. Sanders, C. Yue, Mining least privilege attribute based access control policies, in: Proceedings of the 35th Annual Computer Security Applications Conference, ACSAC ’19, Association for Computing Machinery, New York, NY, USA, 2019, p. 404–416.  doi:10.1145/3359789.3359805.
URL https://doi.org/10.1145/3359789.3359805

  * [17] M. N. Nobi, R. Krishnan, Y. Huang, R. Sandhu, Administration of machine learning based access control, in: Computer Security–ESORICS 2022: 27th European Symposium on Research in Computer Security, Copenhagen, Denmark, September 26–30, 2022, Proceedings, Part II, Springer, 2022, pp. 189–210.
  * [18] M. N. Nobi, R. Krishnan, Y. Huang, M. Shakarami, R. Sandhu, Toward deep learning based access control, in: Proceedings of the Twelveth ACM Conference on Data and Application Security and Privacy, ACM, 2022.  doi:10.1145/3508398.3511497.
URL https://doi.org/10.1145%2F3508398.3511497

  * [19] Z. Jin, L. Xing, Y. Fang, Y. Jia, B. Yuan, Q. Liu, P-verifier, in: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, ACM, 2022.  doi:10.1145/3548606.3560680.
URL https://doi.org/10.1145%2F3548606.3560680

  * [20] A. Outchakoucht, E.-S. Hamza, J. P. Leroy, Dynamic access control policy based on blockchain and machine learning for the internet of things, International Journal of Advanced Computer Science and Applications 8 (7) (2017).
  * [21] A. Chiquito, U. Bodin, O. Schelén, Attribute-based approaches for secure data sharing in industrial contexts, IEEE Access 11 (2023) 10180–10195.  doi:10.1109/ACCESS.2023.3240000.
  * [22] V. C. Hu, D. R. Kuhn, D. F. Ferraiolo, J. Voas, Attribute-based access control, Computer 48 (2) (2015) 85–88.
  * [23] F. Gebali, M. Mamun, Sram physically unclonable functions for smart home iot telehealth environments (2022).
  * [24] A. Ghorbani, A. H. LASHKARI, M. S. I. Mamun, G. D. Gil, Systems and methods for cybersecurity risk assessment of users of a computer network, uS Patent App. 16/753,301 (Jul. 30 2020).
  * [25] K. Al-hammuri, F. Gebali, A. Kanan, I. T. Chelvan, Vision transformer architecture and applications in digital health: a tutorial and survey, Visual Computing for Industry, Biomedicine, and Art 6 (1) (jul 2023).  doi:10.1186/s42492-023-00140-9.
URL https://doi.org/10.1186%2Fs42492-023-00140-9

  * [26] T. Mikolov, K. Chen, G. Corrado, J. Dean, Efficient estimation of word representations in vector space, arXiv preprint arXiv:1301.3781 (2013).
  * [27] K. W. Church, Word2vec, Natural Language Engineering 23 (1) (2017) 155–162.
  * [28] P. T. Hung, K. Yamanishi, Word2vec skip-gram dimensionality selection via sequential normalized maximum likelihood, Entropy 23 (8) (2021) 997.
  * [29] M. Habib, M. Faris, A. Alomari, H. Faris, Altibbivec: a word embedding model for medical and health applications in the arabic language, IEEE Access 9 (2021) 133875–133888.
  * [30] J. Pennington, R. Socher, C. D. Manning, Glove: Global vectors for word representation, in: Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), 2014, pp. 1532–1543.
  * [31] K. Papineni, S. Roukos, T. Ward, W.-J. Zhu, Bleu: a method for automatic evaluation of machine translation, in: Proceedings of the 40th annual meeting of the Association for Computational Linguistics, 2002, pp. 311–318.
  * [32] U. D. HHS, Guidance regarding methods for de-identification of protected health information in accordance with the health insurance portability and accountability act (hipaa) privacy rule, last accessed 05 Mar 2023 (2023).
URL https://www.hhs.gov/hipaa/for-professionals/privacy/special-topics/de-
identification/index.html

  * [33] J. Walonoski, S. Klaus, E. Granger, D. Hall, A. Gregorowicz, G. Neyarapally, A. Watson, J. Eastman, Synthea™ novel coronavirus (covid-19) model and synthetic data set, Intelligence-based medicine 1 (2020) 100007.


# The most general structure of graphs with hamiltonian or hamiltonian
connected square

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,
EU
e-mail<EMAIL_ADDRESS>Herbert Fleischner Institute of Logic and
Computation, Algorithms and Complexity Group, Technical University of Vienna,
Favoritenstrasse 9 - 11, 1040 Wien, Austria, EU
e-mail<EMAIL_ADDRESS>
###### Abstract

On the basis of recent results on hamiltonicity, [4], and hamiltonian
connectedness, [8], in the square of a 2-block, we determine the most general
block-cutvertex structure a graph $G$ may have in order to guarantee that
$G^{2}$ is hamiltonian, hamiltonian connected, respectively. Such an approach
was already developed in [9] for hamiltonian total graphs.

Keywords: hamiltonian cycle, hamiltonian path, block-cutvertex graph, square
of a graph

2010 Mathematics Subject Classification: 05C76, 05C45

##  1 Introduction and Preliminary Discussion

As for standard terminology and other terminology used in this paper, we refer
to the book by Bondy and Murty, [2], and to the papers quoted in the
references. Let $G$ be a connected graph. A _2-block_ is a 2-connected graph
or a block of $G$ containing more than two vertices. The square of a graph
$G$, denoted $G^{2}$, is the graph obtained from $G$ by joining any two
nonadjacent vertices which have a common neighbor, by an edge.

It was shown in 1970 and published in 1974 that the square of every 2-block
contains a hamiltonian cycle, [6]. Key in proving this was the existence of
EPS-graphs $S$ in connected bridgeless graphs $G$, where $S$ is the edge-
disjoint union of a not necessarily connected eulerian subgraph $E$ and a
linear forest $P$, and $S$ is connected and spans $G$, [5]. In subsequent
papers [7], [9] the existence of various types of EPS-graphs was established.
Their relevance was based on the fact that the total graph $T(G)$ of any
connected graph $G$ other than $K_{1}$ is hamiltonian if and only if $G$ has
an EPS-graph, [9]. This and the theory of EPS-graphs led to a description of
the most general block-cutvertex graph $\mbox{bc}(G)$ of a graph $G$ may have
such that $T(G)$ is hamiltonian and if $\mbox{bc}(G)$ does not have the
corresponding structure, then exchanging certain 2-blocks in $G$ with some
special 2-blocks yields a graph $G^{*}$ such that $\mbox{bc}(G)$ and
$\mbox{bc}(G^{*})$ are isomorphic but $T(G^{*})$ is not hamiltonian, [9]. In
dealing with hamiltonian cycles and hamiltonian paths by methods developed up
to that point, it was shown in [7] that in the square of graphs hamiltonicity
and vertex-pancyclicity are equivalent concepts, and so are hamiltonian
connectedness and panconnectedness. In this context Theorem 3 stated below was
established as a tool needed to prove the equivalences just mentioned.

However, in the course of time much shorter proofs of Fleischner’s Theorem
were developed [10], [13]; the same applies to Theorem 3 below, [12]. More
recently, an algorithm yielding a hamiltonian cycle in the square of a 2-block
in linear time, was developed, [1]. The methods developed in these much
shorter proofs (including the algorithm just mentioned) do not seem to yield
short proofs of Theorems 4 and 5 below, [4], [8]. These latter theorems are,
on the other hand, instrumental in proving the central results of this paper,
i.e., Theorems 1 and 2, and related algorithms.

Let $\mbox{bc}(G)$ denote the _block-cutvertex graph_ of $G$. Blocks
corresponding to leaves of $\mbox{bc}(G)$ are called _endblocks_ , otherwise
_innerblocks_. Note that a block in a graph $G$ is either a 2-block or a
bridge of $G$. For each cutvertex $i$ of $G$, let $k_{i}$ be the number of
2-blocks of $G$ which include vertex $i$ and let $\mbox{bn}(i)$ be the number
of nontrivial bridges of $G$ which are incident with vertex $i$. In what
follows a bridge is called nontrivial if it is not incident to a leaf.

Let $H$ be a subgraph of the graph $G$. We define $G-H:=G-E(H)-\\{v\in
V(H):d_{H}(v)=d_{G}(v)\\}$.

In Theorem 1, we introduce an array $m_{i}(B)$ of numbers with an entry for
each pair consisting of a cutvertex $i$ and a 2-block $B$ of $G$. We may think
of this number $m_{i}(B)$ as the number of edges of $B$ incident with $i$
which are possibly contained in a hamiltonian cycle in $G^{2}$.

Statement of Theorem 1 describes the most general block-cutvertex structure a
graph $G$ may have in order to guarantee that $G^{2}$ is hamiltonian using
parameters $m_{i}(B)$ as in [9].

######  Theorem 1.

Let $G$ be a connected graph with at least three vertices. Let the 2-blocks of
$G$ be labelled $B_{1},B_{2},...,B_{n}$. Let the cutvertices of $G$ be
labelled $1,2,...,s$. Suppose there is a labelling $m_{i}(B_{t})$ for each
$i\in\\{1,2,...,s\\}$ and each $t\in\\{1,2,...,n\\}$ such that the following
conditions are fulfilled.

  * 1)

$0\leq m_{i}(B_{t})\leq 2$ for all $i$ and all 2-blocks $B_{t}$;

  * 2)

for 2-block $B_{t}$ $m_{i}(B_{t})=0$ if and only if cutvertex $i$ is not in
$V(B_{t})$;

  * 3)

for 2-block $B_{t}$, $m_{i}(B_{t})\geq\mbox{bn}(i)$, if cutvertex $i\in
V(B_{t})$;

  * 4)

$\mbox{bn}(i)\leq 2$ for all $i\in\\{1,2,...,s\\}$;

  * 5)

$\sum_{i=1}^{s}m_{i}(B_{t})\leq 4$ for each 2-block $B_{t}$ of $G$ and, if
$m_{i}(B_{t})=2$ for some $i$, then $\sum_{i=1}^{s}m_{i}(B_{t})\leq 3$; and

  * 6)

$\sum_{t=1}^{n}m_{i}(B_{t})\geq 2k_{i}+\mbox{bn}(i)-2$ for each
$i\in\\{1,2,...,s\\}$.

Then $G^{2}$ is hamiltonian.

Moreover, if the labelling $m_{i}(B_{t})$ satisfying conditions 1), 2) and 3)
is given and at least one of conditions 4), 5), 6) is violated by some $G$,
then there exists a class of graphs $G^{\prime}$ with non-hamiltonian square
but $\mbox{bc}(G^{\prime})$ and $\mbox{bc}(G)$ are isomorphic.

Also, we obtain a similar result for hamiltonian connectedness (Theorem 2).
Quite surprisingly, its formulation is much simpler than that of Theorem 1.

######  Theorem 2.

Let $G$ be a connected graph such that the following conditions are fulfilled:

  * 1)

there is no nontrivial bridge of $G$;

  * 2)

every block contains at most 2 cutvertices.

Then $G^{2}$ is hamiltonian connected.

Moreover,

  * $\cdot$

if a graph $G$ contains a nontrivial bridge, then $G^{2}$ is not hamiltonian
connected;

  * $\cdot$

if $G$ contains a block containing more than 2 cutvertices, then there is a
graph $G^{\prime}$ such that $\mbox{bc}(G)$ and $\mbox{bc}(G^{\prime})$ are
isomorphic but $(G^{\prime})^{2}$ is not hamiltonian connected.

A fundamental result regarding hamiltonicity in the square of a 2-block is the
following theorem.

######  Theorem 3.

__[_7]_ Suppose $v$ and $w$ are two arbitrarily chosen vertices of a $2$-block
$G$. Then $G^{2}$ contains a hamiltonian cycle $C$ such that the edges of $C$
incident to $v$ are in $G$ and at least one of the edges of $C$ incident to
$w$ is in $G$. Furthermore, if $v$ and $w$ are adjacent in $G$, then these are
three different edges.

The hamiltonian theme in the square of a 2-block has been recently revisited
([3], [4], [8]), yielding the following results which are essential for this
paper.

A graph $G$ is said to have the _$\mathcal{H}_{k}$ property_ if for any given
vertices $x_{1},...,x_{k}$ there is a hamiltonian cycle in $G^{2}$ containing
distinct edges $x_{1}y_{1},...,x_{k}y_{k}$ of $G$.

######  Theorem 4.

__[_4]_ Given a 2-block $G$ on at least 4 vertices, then $G$ has the
$\mathcal{H}_{4}$ property, and there are 2-blocks of arbitrary order greater
than 4 without the $\mathcal{H}_{5}$ property.

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_. Let
$A=\\{x_{1},x_{2},...,x_{k}\\}$ be a set of $k\geq 3$ distinct vertices in
$G$. An $x_{1}x_{2}$-hamiltonian path in $G^{2}$ which contains $k-2$ distinct
edges $x_{i}y_{i}\in E(G),i=3,...,k$, is said to be $\mathcal{F}_{k}$. A graph
$G$ is said to have the _$\mathcal{F}_{k}$ property_ if, for any set
$A=\\{x_{1},x_{2},...,x_{k}\\}\subseteq V(G)$, there is an $\mathcal{F}_{k}$
$x_{1}x_{2}$-hamiltonian path in $G^{2}$.

######  Theorem 5.

__[_8]_ Every 2-block on at least 4 vertices has the $\mathcal{F}_{4}$
property.

A graph $G$ is said to have the _strong $\mathcal{F}_{3}$ property_ if, for
any set of 3 vertices $\\{x_{1},x_{2},x_{3}\\}$ in $G$, there is an
$x_{1}x_{2}$-hamiltonian path in $G^{2}$ containing distinct edges
$x_{3}z_{3},x_{i}z_{i}\in E(G)$ for a given $i\in\\{1,2\\}$. Such an
$x_{1}x_{2}$-hamiltonian path in $G^{2}$ is called a strong $\mathcal{F}_{3}$
$x_{1}x_{2}$-hamiltonian path.

######  Theorem 6.

__[_8]_ Every 2-block has the strong $\mathcal{F}_{3}$ property.

######  Theorem 7.

__[_8]_ Let $G$ be a $2$-connected graph and let $x,y$ be two vertices in $G$.
Then $G^{2}$ has an $xy$-hamiltonian path $P(x,y)$ such that

(i) $xz\in E(G)\cap E(P(x,y))$ for some $z\in V(G)$, and

(ii) either $yw\in E(G)\cap E(P(x,y))$ for some $w\in V(G)$, or else $P(x,y)$
contains an edge $uv$ for some vertices $u,v\in N(y)$.

##  2 Proofs and algorithms

PROOF OF THEOREM 1

###### Proof.

Set $P_{0}=G-\cup_{t=1}^{n}B_{t}$. Then every component of $P_{0}$ is a tree.
Since by 4) $\mbox{bn}(i)\leq 2$ every component of $P_{0}$ is even a
caterpillar.

For every caterpillar $T$ of $P_{0}$ except $T=K_{2}$ we have the following
observation which can be proved easily.

_Observation: Let $T$ be a caterpillar with at least three vertices and
$P=x_{1}x_{2}...x_{m}$ be some longest path in $T$. Then $T^{2}$ contains a
hamiltonian cycle containing edges $x_{1}x_{2},x_{m-1}x_{m}$ and different
edges $u_{j}v_{j}$, where $u_{j},v_{j}\in N_{G}(x_{j})$ for $j=2,3,...,m-1$._

See Figure 1 for illustration in which for $x_{3}$ we have $u_{3}=x_{2}$ and
$v_{3}=x_{4}$.

Figure 1: Hamiltonian cycle in a caterpillar for $m=7$ (bold edges)

Every 2-block $B_{t}$ contains a hamitonian cycle in $(B_{t})^{2}$ which is
one of two types depending on labellings $m_{i}(B_{t})$:

Let $m_{i}(B_{t})\neq 2$ for every $i=1,2,...,s$. If $B_{t}\cong C_{3}$, then
we set $C_{t}=B_{t}$. Otherwise for at most 4 cutvertices $a,b,c,d$ it holds
that $m_{j}(B_{t})=1$ for $j=a,b,c,d$ by condition 5). By Theorem 4,
$(B_{t})^{2}$ has a hamiltonian cycle $C_{t}$ containing 4 different edges
$aa^{\prime},bb^{\prime},cc^{\prime},dd^{\prime}$ of $B_{t}$.

If $m_{i}(B_{t})=2$ for some $i\in\\{1,2,...,s\\}$, then at most one cutvertex
$a$ has $m_{a}(B_{t})=1$ by condition 5). By Theorem 3, $(B_{t})^{2}$ has a
hamiltonian cycle $C_{t}$ containing 3 different edges
$ii^{\prime},ii^{\prime\prime},aa^{\prime}$ of $B_{t}$.

The union of hamiltonian cycles $C_{t}$ in $(B_{t})^{2}$, for $t=1,2,...,n$,
hamiltonian cycles in the square of each catepillar (nontrivial component of
$P_{0}$) and trivial components of $P_{0}$ is a connected spanning subgraph
$S$ of $G^{2}$.

We construct a hamiltonian cycle $C$ in $G^{2}$ from $S$ repeating step by
step the following procedure for every cutvertex $i$ of $G$ with $m_{i}(B)\geq
1$ for some 2-block $B$.

If $i$ does not exist, then $n=0$ and $G=P_{0}$ is a caterpillar. Hence $S$ is
a hamiltonian cycle in $G^{2}$. Otherwise we join all hamiltonian cycles from
$S$ containing $i$ together with trivial components of $P_{0}$ containing $i$
to one cycle in the following way.

First assume that $\mbox{bn}(i)=0$.

By condition 6) we have $\sum_{t=1}^{n}m_{i}(B_{t})\geq 2k_{i}-2$. Without
loss of generality for $k_{i}>1$ we may assume that $m_{i}(B_{1})\geq 1$,
$m_{i}(B_{2})\geq 1$ and
$m_{i}(B_{3})=m_{i}(B_{4})=\cdots=m_{i}(B_{k_{i}})=2$, where $m_{i}(B_{t})$
corresponds to the number of edges of $B_{t}$ incident to $i$ in $C_{t}$. If
$k_{i}=1$, then by condition 2) we have $m_{i}(B_{1})\geq 1$.

We find a cycle $C^{i}$ on $\cup_{r=1}^{k_{i}}V(C_{r})\cup L$, where $L$ is
the set of all leaves incident to $i$, by appropriately replacing edges of
$C_{r}\cap B_{r}$, $r=1,2,...,k_{i}$, incident to $i$ (guaranteed by
definition of $m_{i}(B_{t})$) with edges of $G^{2}$ joining vertices in
different $C_{r}$ adjacent to $i$ and leaves adjacent to $i$. Note that we
preserve properties given by $m_{j}(B_{t})$ for all $j\neq i$.

Now assume that $\mbox{bn}(i)=1$.

By condition 6) we have $\sum_{t=1}^{n}m_{i}(B_{t})\geq 2k_{i}+1-2=2k_{i}-1$.
Without loss of generality we may assume that $m_{i}(B_{1})\geq 1$ and
$m_{i}(B_{2})=m_{i}(B_{3})=\cdots=m_{i}(B_{k_{i}})=2$, where $m_{i}(B_{t})$
corresponds to the number of edges of $B_{t}$ incident to $i$ in $C_{t}$. Let
$T$ be the component of $P_{0}$ containing $i$.

If $T=K_{2}=ii^{\prime}$, where $i^{\prime}$ is also a cutvertex of $G$ with
$m_{i^{\prime}}(B)\geq 1$ ($T$ is a trivial component of $P_{0}$), then we
find a cycle $C^{i}$ on $\cup_{r=1}^{k_{i}}V(C_{r})\cup V(T)$ containing the
edge $ii^{\prime}$ by appropriately replacing edges of $C_{r}\cap B_{r}$,
$r=1,2,...,k_{i}$, incident to $i$ (guaranteed by definition of
$m_{i}(B_{t})$) with edges of $G^{2}$ joining $i^{\prime}$ and vertices in
different $C_{r}$ adjacent to $i$. Also here we preserve properties given by
$m_{j}(B_{t})$ for all $j\neq i$.

If $T$ is a nontrivial component of $P_{0}$, then $T^{2}$ contains a
hamiltonian cycle $C_{T}$ containing end-edges of any fixed longest path $P$
in $T$ (we choose end-edges containing cutvertices of $G$ with
$m_{i}(B_{t})\geq 1$) - see Observation above. Again we find a cycle $C^{i}$
on $\cup_{r=1}^{k_{i}}V(C_{r})\cup V(C_{T})$ by appropriately replacing edges
of $C_{r}\cap B_{r}$, $r=1,2,...,k_{i}$, incident to $i$ (guaranteed by
definition of $m_{i}(B_{t})$) and the end-edge $ii^{*}$ of $P$ with edges of
$G^{2}$ joining $i^{*}$ and vertices in different $C_{r}$ adjacent to $i$.
Again we preserve properties given by $m_{j}(B_{t})$ for all $j\neq i$ and by
$C_{T}$.

Finally assume that $\mbox{bn}(i)=2$.

By condition 6) we have $\sum_{t=1}^{n}m_{i}(B_{t})\geq 2k_{i}+2-2=2k_{i}$. It
follows necessarily that
$m_{i}(B_{1})=m_{i}(B_{2})=\cdots=m_{i}(B_{k_{i}})=2$, where $m_{i}(B_{t})$
corresponds to the number of edges of $B_{t}$ incident to $i$ in $C_{t}$.

Let $T$ be the nontrivial component of $P_{0}$ containing $i$. Note that $i$
is not an endvertex of $T$ because of $\mbox{bn}(i)=2$. Then $T^{2}$ contains
a hamiltonian cycle $C_{T}$ containing end-edges of any fixed longest path in
$T$ (we choose end-edges containing cutvertices of $G$ with $m_{i}(B_{t})\geq
1$) and an edge $u_{i}v_{i}$ of $G^{2}$ where $u_{i},v_{i}\in N_{G}(i)$ (see
Observation above). We find a cycle $C^{i}$ on $\cup_{r=1}^{k_{i}}V(C_{r})\cup
V(C_{T})$ by appropriately replacing edges of $C_{r}\cap B_{r}$,
$r=1,2,...,k_{i}$, incident to $i$ (guaranteed by definition of
$m_{i}(B_{t})$) and the edge $u_{i}v_{i}$ of $P$ with edges of $G^{2}$ joining
$u_{i},v_{i}$ and vertices in different $C_{r}$ adjacent to $i$ if $k_{i}>1$.
If, however, $k_{i}=1$, then $u_{i}$ and $v_{i}$ are joined to the neighbors
of $C_{r}\cap B_{r}$ in $N_{G}(i)$. Also here we preserve properties given by
$m_{j}(B_{t})$ for all $j\neq i$ and by $C_{T}$.

Now we choose next cutvertex $i$ with $m_{i}(B)\geq 1$ for some 2-block $B$
successively and we use all cycles formed in the previous steps instead of
previously formed cycles. Note that we preserve all properties given by
$m_{j}(B)$ for all $j\neq i$ in every case. We stop with the hamiltonian cycle
in $G^{2}$ as required.

Now assume that there is no labelling satisfying conditions 1) - 6), that is,
the labelling $m_{i}(B_{t})$ satisfying conditions 1), 2) and 3) is given and
at least one of conditions 4), 5), 6) is violated. We show that there exists a
class of graphs $G^{\prime}$ with non-hamiltonian square but
$\mbox{bc}(G^{\prime})$ and $\mbox{bc}(G)$ are isomorphic.

Figure 2: Graphs without hamiltonian square

_Condition 4) does not hold._

Hence $\mbox{bn}(i)\geq 3$ for at least one $i\in\\{1,2,...,s\\}$. Clearly
this is a class of graphs $G^{\prime}$ such that the square of every such
graph $G^{\prime}$ does not contain a hamiltonian cycle (if we try to
construct a hamiltonian cycle in the square, then the degree of the cutvertex
$i$ is at least 3, a contradiction), e.g. see the graph in Figure 2 a), where
$H_{1}$ is an arbitrary connected graphs, $H_{2}$, $H_{3}$, $H_{4}$ are
arbitrary connected graphs with at least one edge each and $\mbox{bn}(i)=3$.
Note that conditions 5) and 6) may hold.

_Condition 5) does not hold._

Hence $\sum_{i=1}^{s}m_{i}(B)\geq 5$ for some 2-block $B$ and $m_{i}(B)<2$ for
all $i$ or $\sum_{j=1}^{s}m_{j}(B)\geq 4$ for some 2-block $B$ and
$m_{i}(B)=2$ for some $i\in\\{1,2,...,s\\}$.

First suppose that $k=\sum_{i=1}^{s}m_{i}(B)\geq 5$ for some 2-block $B$ of
$G$ and $m_{i}(B)<2$ for all $i$. Clearly $B$ has exactly $k$ cutvertices by
condition 2). Then we exhange $B$ with $K_{2,k}$ where $k$ 2-valent vertices
are cutvertices of $G$ and all other blocks with arbitrary blocks to get a
class of graphs $G^{\prime}$ such that $\mbox{bc}(G^{\prime})$ and
$\mbox{bc}(G)$ are isomorphic. The square of every such graph $G^{\prime}$
does not contain a hamiltonian cycle (if we try to construct a hamiltonian
cycle in the square, then the degree of at least one of the two $k$-valent
vertices of $K_{2,k}$ is at least 3, a contradiction), e.g. see the graph in
Figure 2 b), where $k=5$ and $H_{1},...,H_{5}$ are arbitrary connected graphs
with at least one edge each. Note that conditions 4), 6) and the second part
of condition 5) may hold.

Now suppose that $\sum_{j=1}^{s}m_{j}(B)\geq 4$ for some 2-block $B$ and
$m_{i}(B)=2$ for some $i$. If $B$ contains at least 5 cutvertices of $G$, then
we continue similarly as above. If $B$ contains $k$ cutvertices of $G$ where
$2\leq k\leq 4$, then without loss of generality we may assume that we tried
to set the labelling $m_{i}(B_{t})$ satisfying firstly condition 5) and
subsequently condition 6). Hence $\mbox{bn}(i)\geq 2$ and $\mbox{bn}(j)\geq 2$
where $j$ is the second cutvertex of $G$ in $B$ if $k=2$, otherwise we find a
labelling $m_{i}(B_{t})$ satisfying condition 5), a contradiction (see
Algorithm 1 cases e) and f) below).

For $k=3,4$ we exhange $B$ with a cycle $C_{k}$ to get a class of graphs
$G^{\prime}$ such that $\mbox{bc}(G^{\prime})$ and $\mbox{bc}(G)$ are
isomorphic. The square of every such graph $G^{\prime}$ does not contain a
hamiltonian cycle (if we try to construct a hamiltonian cycle in the square,
then the degree of the cutvertex $i$ is at least 3, a contradiction), e.g. see
the graph in Figure 2 c), where $k=3$ and $H_{1},...,H_{4}$ are arbitrary
connected graphs with at least one edge each. Note that conditions 4), 6) and
the first part of condition 5) may hold.

For $k=2$, we exchange $B$ with $K_{2,3}$, where two of the three 2-valent
vertices are $i$ and $j$, to get a class of graphs $G^{\prime}$ such that
$\mbox{bc}(G^{\prime})$ and $\mbox{bc}(G)$ are isomorphic. The square of every
such graph $G^{\prime}$ does not contain a hamiltonian cycle (it is not
possible to find a hamiltonian cycle in the square containing the third
2-valent vertex different from $i$, $j$, a contradiction), e.g. see the graph
in Figure 2 d), where $H_{1},...,H_{4}$ are arbitrary connected graphs with at
least one edge each. Note that conditions 4), 6) and the first part of
condition 5) may hold.

_Condition 6) does not hold._

Hence $\sum_{t=1}^{n}m_{i}(B_{t})<2k_{i}+\mbox{bn}(i)-2$ for some $i$ and
consequently $m_{i}(B_{t})=1$ for at least $3-\mbox{bn}(i)$ 2-blocks
containing $i$. Note that, clearly, $\mbox{bn}(i)<2$ with respect to condition
3).

Let $r$ be the number of 2-blocks with $m_{i}(B_{t})=1$. Each of these
2-blocks contains either exactly 2 cutvertices of $G$ or at least 3
cutvertices of $G$. Note that for 2-blocks containing only cutvertex $i$ we
have $m_{i}(B_{t})=2$ (see Algorithm 1 case d) below). We exchange every
2-block containing exactly 2 cutvertices of $G$ with a cycle $C_{3}$ and every
2-block containing $k$ cutvertices of $G$, $k\geq 3$, with a cycle $C_{k}$. In
the first case note that we assume without loss of generality that there is no
labelling such that we switch values 1 and 2 for both cutvertices of this
2-block to get a permissible labelling (again see Algorithm 1 case e) below).

Since $r\geq 3-\mbox{bn}(i)$, by the exchanging 2-block mentioned above we get
a class of graphs $G^{\prime}$ such that $\mbox{bc}(G^{\prime})$ and
$\mbox{bc}(G)$ are isomorphic. The square of every such graph $G^{\prime}$
does not contain a hamiltonian cycle (if we try to construct a hamiltonian
cycle in the square, then the degree of the cutvertex $i$ is at least 3, a
contradiction), e.g. see graphs in Figure 2 $e_{1}$) and $e_{2}$). For the
graph in Figure 2 $e_{1}$) it holds that $r=3-\mbox{bn}(i)=3-1=2$, the 2-block
$B_{1}$ has exactly 2 cutvertices of $G$, the 2-block $B_{2}$ has $k=3$
cutvertices of $G$ (and hence $B_{1}$, $B_{2}$ are isomorphic to $C_{3}$) and
$H_{1},...,H_{5}$ are arbitrary connected graphs with at least one edge. For
the graph in Figure 2 $e_{2}$) it holds that $r=3-\mbox{bn}(i)=3-0=3$, the
2-block $B_{1}$ has exactly 2 cutvertices of $G$, the 2-block $B_{2}$ has
$k=3$ cutvertices of $G$, the 2-block $B_{3}$ has $k=4$ cutvertices of $G$
(hence $B_{1}$, $B_{2}$ are isomorphic to $C_{3}$ and $B_{3}$ is isomorphic to
$C_{4}$) and $H_{1},...,H_{7}$ are arbitrary connected graphs with at least
one edge. Note that conditions 4) and 5) may hold.

This finishes the proof of Theorem 1. ∎

If there is a graph $G$ such that every labelling $m_{i}(B_{t})$ violates at
least one of the conditions 4) - 6) of Theorem 1, then there is a graph
$G^{\prime}$ with $\mbox{bc}(G^{\prime})=\mbox{bc}(G)$ such that
$(G^{\prime})^{2}$ is not hamiltonian as it has been shown in the proof of
Theorem 1. On the other hand, if we are able to construct a labelling
$m_{i}(B_{t})$ satisfying conditions 1) - 6) using the following algorithm,
then $G^{2}$ is hamiltonian as it has been shown in the proof of Theorem 1.

_ALGORITHM 1:_

Set $P_{0}=G-\cup_{t=1}^{n}B_{t}$. If any component of $P_{0}$ is not a
caterpillar, then $\mbox{bn}(i)\geq 3$ for some $i\in\\{1,2,...,s\\}$
contradicting condition 4) in Theorem 1 and $G^{2}$ is not hamiltonian (e.g.
see Figure 2 a)). STOP.

If $G=P_{0}$, then $G$ is a caterpillar, $n=0$ and $G^{2}$ is hamiltonian (see
Observation in the proof of Theorem 1) and $m_{i}(B_{t})$ is not defined
($n=0$). STOP.

If $G$ is a 2-block, $G^{2}$ is hamiltonian by Theorem 3 and $m_{i}(B_{t})$ is
not defined ($s=0$ and $n=1$). STOP.

We set $G_{0}=G-P_{0}$ and $m_{i}(B_{t})=0$ if $i\notin V(B_{t})$ for
$i\in\\{1,2,...,s\\}$ and $t\in\\{1,2,...,n\\}$.

START

We choose a 2-block $B$ containing at most 1 cutvertex of $G_{0}$. Note that
$B$ is either a component of $G_{0}$ or an endblock of some component of
$G_{0}$. If such endblock does not exist, we choose 2-block $B$ as a component
of $G_{0}-H$ or an endblock of $G_{0}-H$ where $H$ is the union of all
2-blocks for which the labelling $m_{i}(B_{t})$ is already set. Let
$c_{1},c_{2},...,c_{k}$ be all cutvertices of $G$ contained in $B$, $k\geq 1$.

  * a)

If $k\geq 5$, then by condition 2) $m_{c_{i}}(B)\geq 1$ for $i=1,2,...,k$.
Hence condition 5) in Theorem 1 does not hold and $G^{2}$ may not be
hamiltonian (e.g. see Figure 2 b)). STOP.

  * b)

If $k\geq 3$ and $\mbox{bn}(c_{i})=2$ for some $i\in\\{1,2,...,k\\}$ , then by
condition 3) $m_{c_{i}}(B)=2$ and by 2) $m_{c_{j}}(B)\geq 1$ for
$j=1,2,...,k$. Hence condition 5) in Theorem 1 does not hold and $G^{2}$ may
not be hamiltonian (e.g. see Figure 2 c)). STOP.

  * c)

If $k=2$ and $\mbox{bn}(c_{1})=\mbox{bn}(c_{2})=2$, then by condition 3)
$m_{c_{1}}(B)=2$ and $m_{c_{2}}(B)=2$. Hence condition 5) in Theorem 1 does
not hold and $G^{2}$ may not be hamiltonian (e.g. see Figure 2 d)). STOP.

  * d)

If $k=1$, then we set $m_{c_{1}}(B)=2$ (we maximize values $m_{i}(B_{t})$ with
respect to condition 6) in Theorem 1). Note that, if the labelling
$m_{i}(B_{t})$ is set for all 2-blocks incident with $c_{1}$, then condition
6) holds for cutvertex $c_{1}$ with respect to the choice of $B$.

If the labelling $m_{i}(B_{t})$ is set for all 2-blocks of $G$, then the
labelling $m_{i}(B_{t})$ satisfies the conditions of Theorem 1 and $G^{2}$ is
hamiltonian. STOP.

Otherwise we go to START.

  * e)

If $k=2$ and $\mbox{bn}(c_{i})\leq 1$ for $i\in\\{1,2\\}$, then we set
$m_{c_{1}}(B)$ and $m_{c_{2}}(B)$ in the following way (without loss of
generality $i=1$).

Let $\mbox{bn}(c_{2})=2$. Then we set $m_{c_{1}}(B)=1$ and $m_{c_{2}}(B)=2$
with respect to conditions 2), 3) and 5).

Let $\mbox{bn}(c_{2})\leq 1$. Then for at least one of $c_{1}$, $c_{2}$ it
holds that $m_{c_{j}}(B_{t})$ for $j\in\\{1,2\\}$ is set for all 2-blocks
$B_{t}$ except $B$ with respect to the choice of $B$ (again without loss of
generality $j=1$). We set $m_{c_{1}}(B)=1$ and we verify condition 6) for
$c_{1}$. If it holds, then we set $m_{c_{2}}(B)=2$ (again we maximize values
$m_{i}(B_{t})$ with respect to condition 6)). If condition 6) for $c_{1}$ does
not hold for $m_{c_{1}}(B)=1$, then we set $m_{c_{1}}(B)=2$ and
$m_{c_{2}}(B)=1$.

Now in both cases we verify condition 6) for $c_{1}$ and $c_{2}$ if the
labelling $m_{c_{1}}(B_{t})$ and $m_{c_{2}}(B_{t})$ is set for all 2-blocks
$B_{t}$.

If condition 6) does not hold in at least one case, then $G^{2}$ may not be
hamiltonian (e.g. see Figure 2 $e_{1})$). STOP.

Hence suppose that condition 6) holds for $c_{1}$, $c_{2}$ if
$m_{c_{1}}(B_{t})$, $m_{c_{2}}(B_{t})$ is set for all $B_{t}$, respectively.

If the labelling $m_{i}(B_{t})$ is set for all 2-blocks, then the labelling
$m_{i}(B_{t})$ satisfies the conditions of Theorem 1 and $G^{2}$ is
hamiltonian. STOP.

Otherwise we go to START.

  * f)

If $k\in\\{3,4\\}$ and $\mbox{bn}(c_{i})\leq 1$, then we set $m_{c_{i}}(B)=1$
for $i=1,2,...,k$. We verify condition 6) for all $c_{i}$ if the labelling
$m_{c_{i}}(B_{t})$ is set for all 2-blocks $B_{t}$.

If condition 6) does not hold in at least one case, then $G^{2}$ may not be
hamiltonian (e.g. see Figure 2 $e_{2})$). STOP.

Hence suppose that condition 6) holds for all $c_{i}$, $i=1,2,...,k$, for
which $m_{c_{i}}(B_{t})$ is set for all $B_{t}$.

If the labelling $m_{i}(B_{t})$ is set for all 2-blocks, then the labelling
$m_{i}(B_{t})$ satisfies the conditions of Theorem 1 and $G^{2}$ is
hamiltonian. STOP.

Otherwise we go to START.

PROOF OF THEOREM 2

###### Proof.

Let $x,y\in V(G)$. First we prove that there exists an $xy$-hamiltonian path
$P$ in $G^{2}$ if there is no nontrivial bridge of $G$ and every block
contains at most 2 cutvertices.

(A) Suppose that $x$ and $y$ are in the same block $B$ of $G$. We proceed by
induction on $n$, where $n$ is the number of blocks of $G$, $n\geq 1$.

For $n=1$, clearly $G=B$. If $B=K_{2}=xy$, then $G$ is also the
$xy$-hamiltonian path in $G^{2}$ as required. If $B$ is a 2-block, then by
Theorem 6, $G^{2}=B^{2}$ contains an $xy$-hamiltonian path $P$ as required.

Now suppose that the statement of Theorem 2 is true for every graph with $n$
blocks and $G$ is a graph with $n+1$ blocks, $n\geq 1$. We distinguish 2
cases.

  * •

$B$ has exactly one cutvertex $c$.

Without loss of generality we assume that $x\neq c$. If $B$ is a 2-block, then
by Theorem 6, $B^{2}$ contains an $xy$-hamiltonian path $P_{B}$ containing an
edge $cy^{\prime}$ where $y^{\prime}$ is a neighbor of $c$ in $B$. Note that
$y^{\prime}=x$ or $c=y$ is possible. If $B=K_{2}$, then $B=xy=y^{\prime}c$ and
$P_{B}=xy$ is an $xc$-hamiltonian path in $B^{2}$. By the induction hypothesis
$(G-B)^{2}$ contains a $cc^{\prime}$-hamiltonian path $P_{G}$ where
$c^{\prime}$ is a neighbor of $c$ in $G-B$. Then $P=P_{B}\cup
P_{G}-cy^{\prime}+y^{\prime}c^{\prime}$ is an $xy$-hamiltonian path in $G^{2}$
as required.

  * •

$B$ has two cutvertices $c_{1}$, $c_{2}$.

We denote by $G_{1}$, $G_{2}$ the two components of $G-B$ such that $c_{i}\in
V(G_{i})$ and let $c^{\prime}_{i}$ be a neighbor of $c_{i}$ in $G_{i}$,
$i=1,2$. By the induction hypothesis $(G_{i})^{2}$ contains a
$c_{i}c^{\prime}_{i}$-hamiltonian path $P_{G_{i}}$, $i=1,2$.

    * a)

$c_{i}\notin\\{x,y\\}$ ($x$ and $y$ are not cutvertices).

By Theorem 5, $B^{2}$ contains an $xy$-hamiltonian path $P_{B}$ containing the
edges $c_{i}z_{i}$ where $z_{i}$ is a neighbor of $c_{i}$ in $B$, $i=1,2$.
Note that $z_{i}\in\\{x,y\\}$ is possible.

    * b)

Up to symmetry $c_{1}=x$ and $c_{2}\neq y$ (either $x$ or $y$ is a cutvertex
of $G$).

By Theorem 6, $B^{2}$ contains an $xy$-hamiltonian path $P_{B}$ containing the
edges $c_{i}z_{i}$ where $z_{i}$ is a neighbor of $c_{i}$ in $B$, $i=1,2$.
Note that $z_{1}=c_{2}$ or $z_{2}=y$ is possible.

    * c)

$c_{1}=x$ and $c_{2}=y$ (similarly $c_{1}=y$ and $c_{2}=x$).

By Theorem 7, $B^{2}$ contains an $xy$-hamiltonian path $P_{B}$ containing
either the edges $c_{i}z_{i}$ where $z_{i}$ is a neighbor of $c_{i}$ in $B$,
$i=1,2$, or the edges $c_{1}z_{1}$, $uv$ where $z_{1}$ is a neighbor of
$c_{1}$ in $B$ and $u,v$ are neighbors of $c_{2}$ in $B$.

In all cases except the case c), if $uv$ is the edge of $P_{B}$,

$P=P_{G_{1}}\cup P_{B}\cup
P_{G_{2}}-\\{c_{1}z_{1},c_{2}z_{2}\\}\cup\\{c^{\prime}_{1}z_{1},c^{\prime}_{2}z_{2}\\}$

is an $xy$-hamiltonian path in $G^{2}$ as required.

It remains to find an $xy$-hamiltonian path in $G^{2}$ if $uv$ is the edge of
$P_{B}$.

If $G_{2}=K_{2}=c_{2}c^{\prime}_{2}$, then

$P=P_{G_{1}}\cup
P_{B}-\\{c_{1}z_{1},uv,c_{2}c^{\prime}_{2}\\}\cup\\{c^{\prime}_{1}z_{1},c^{\prime}_{2}u,c^{\prime}_{2}v\\}$

is an $xy$-hamiltonian path in $G^{2}$ as required.

If $G_{2}\neq K_{2}$, then we prove that $(G_{2})^{2}$ contains a hamiltonian
cycle $C$ containing edges $c_{2}u_{2}$, $c_{2}v_{2}$ of $G_{2}$. Let
$B_{1},B_{2},...,B_{k}$ be all 2-blocks of $G_{2}$ containing $c_{2}$. By
Theorem 3, for $i=1,2,...,k$, $(B_{i})^{2}$ contains a hamiltonian cycle
$C^{\prime}_{i}$ containing three different edges $c_{2}u_{2}^{i}$,
$c_{2}v_{2}^{i}$, $y_{i}y^{\prime}_{i}$ of $B_{i}$ where $y_{i}$ is the second
cutvertex of $G_{2}$ in $B_{i}$ if it exists.

If $y_{i}$ exists, then we denote by $H_{i}$ a component of
$G_{2}-(B_{i}-y_{i})$ containing $y_{i}$. By the induction hypothesis
$(H_{i})^{2}$ contains a $y_{i}d_{i}$-hamiltonian path $P_{i}$ where $d_{i}$
is a neighbor of $y_{i}$ in $H_{i}$. Then we set $C_{i}=C^{\prime}_{i}\cup
P_{i}-y_{i}y^{\prime}_{i}+y^{\prime}_{i}d_{i}$. If $y_{i}$ does not exist,
then we set $C_{i}=C^{\prime}_{i}$.

Let $T$ be the set of all leaves of $G_{2}$ adjacent to $c_{2}$. Then we find
a cycle $C$ on $\cup_{i=1}^{k}V(C_{i})\cup T$ by appropriately replacing edges
$c_{2}u_{2}^{i}$, $c_{2}v_{2}^{i}$ with edges of $G^{2}$ joining $u_{2}^{i}$,
$v_{2}^{i}$ in different $C_{i}$ and leaves adjacent to $c_{2}$ (similarly as
in the proof of Theorem 1) such that we preserve two edges ($c_{2}u_{2}^{i}$,
$c_{2}v_{2}^{i}$ or $c_{2}l_{1}$, $c_{2}l_{2}$ where $l_{1},l_{2}$ are two
leaves of $G_{2}$ adjacent to $c_{2}$) as $c_{2}u_{2}$, $c_{2}v_{2}$.

Now

$P=P_{G_{1}}\cup P_{B}\cup
C-\\{c_{1}z_{1},uv,c_{2}u_{2},c_{2}v_{2}\\}\cup\\{c^{\prime}_{1}z_{1},u_{2}u,v_{2}v\\}$

is an $xy$-hamiltonian path in $G^{2}$ as required.

(B) Suppose that $x$ and $y$ are in different blocks of $G$.

Let $P_{G}$ be any $xy$-path in $G$ and $c\in V(P_{G})\setminus\\{x,y\\}$ be a
cutvertex of $G$. Let $K$ be the component of $G-c$ containing $x$,
$G_{y}=G-V(K)$ and $G_{x}=G-G_{y}$. Clearly $G_{x}\cup G_{y}=G$ and $G_{x}\cap
G_{y}=c$. If $G_{x}$, $G_{y}$ are isomorphic to $K_{2}$, then we set
$P_{x}=G_{x}$, $P_{y}=G_{y}$, respectively. If $G_{x}$, $G_{y}$ are 2-blocks,
then $(G_{x})^{2}$, $(G_{y})^{2}$ contains an $xc$-hamiltonian path $P_{x}$, a
$cy$-hamiltonian path $P_{y}$ by Theorem 6, respectively. We proceed by
induction on $n$, where $n$ is the number of blocks of $G$, $n\geq 2$.

First assume that $G$ has exactly 2 blocks. Hence $G_{x}$, $G_{y}$ are
isomorphic to $K_{2}$ or 2-blocks and $P=P_{x}\cup P_{y}$ is an
$xy$-hamiltonian path in $G^{2}$ as required.

Now suppose that the statement of Theorem 2 is true for every graph with $n$
blocks and $G$ is a graph with $n+1$ blocks, $n\geq 2$. If $G_{x}$, $G_{y}$ is
not a block, then by the induction hypothesis $(G_{x})^{2}$, $(G_{y})^{2}$
contains an $xc$-hamiltonian path $P_{x}$, a $cy$-hamiltonian path $P_{y}$,
respectively. Then $P=P_{x}\cup P_{y}$ is an $xy$-hamiltonian path in $G^{2}$
as required.

Now it remains to prove that if there is a nontrivial bridge of $G$, then
$G^{2}$ is not hamiltonian connected and if $G$ contains a block containing
more than 2 cutvertices, then there is a graph $G^{\prime}$ such that
$\mbox{bc}(G)$ and $\mbox{bc}(G^{\prime})$ are isomorphic but
$(G^{\prime})^{2}$ is not hamiltonian connected.

Clearly, if there exists a nontrivial bridge $xy$ in $G$, then there is no
$xy$-hamiltonian path in $G^{2}$ and $G^{2}$ is not hamiltonian connected.

Figure 3: Graphs without $xy$-hamiltonian path in the square

Finally assume that $G$ contains a block $B$ containing $r$ cutvertices, where
$r>2$. Then we exhange $B$ with a cycle $C_{r}$ and all other blocks with
arbitrary blocks to get a class of graphs $G^{\prime}$ such that
$\mbox{bc}(G^{\prime})$ and $\mbox{bc}(G)$ are isomorphic. Clearly the square
of every such graph $G^{\prime}$ does not contain a hamiltonian path between
arbitrary two cutvertices of $G^{\prime}$ in $C_{r}$ and hence
$(G^{\prime})^{2}$ is not hamiltonian connected, e.g. with Figure 3, where
$r=3$ and $H_{1},H_{2},H_{3}$ are arbitrary connected graphs with at least one
edge. ∎

Similarly as for Theorem 1 we state the following algorithm to verify
conditions of Theorem 2.

_ALGORITHM 2:_

Let $G^{\prime}=G-S$ where $S$ is the set of all endblocks of $G$. Let
$\mbox{cvn}_{G}(B)$ be the number of cutvertices of $G$ in $B$.

START

Find an endblock $B$ of $G^{\prime}$.

  * •

If $B$ is a bridge of $G^{\prime}$, then $B$ is a nontrivial bridge of $G$ and
$G^{2}$ is not hamiltonian connected. STOP.

  * •

Let $B$ be a 2-block.

    * –

If $\mbox{cvn}_{G}(B)>2$, then $G^{2}$ may not be hamiltonian connected (e.g.
see Figure 3). STOP.

    * –

If $\mbox{cvn}_{G}(B)\leq 2$, then $G^{\prime}:=G^{\prime}-B$.

      * *

If $G^{\prime}=\emptyset$, then $G^{2}$ is hamiltonian connected. STOP.

      * *

If $G^{\prime}\neq\emptyset$, then go to START.

In both algorithms in this paper, determining blocks and especially endblocks
and bridges, cutvertices, block-cutvertex graphs, and the parameters
$\mbox{bn}(i)$, $\mbox{cvn}_{G}(B)$ can be determined in polynomial time.

As a consequence, polynomial running time in Algorithm 2 is guaranteed. For,
determining (potentially) not being Hamiltonian connected, can be determined
instantly once a nontrivial bridge, a block with more than 2 cutvertices has
been found. And deleting an endblock reduces the size of $G^{\prime}$
linearly.

Now consider the running time of Algorithm 1. The first decision to be made is
whether $P_{0}$ is a forest of caterpillars – this can be done in linear time.
After that, at every step ’one chooses a 2-block $B$ as a component of
$G_{0}-H$ or an endblock of $G_{0}-H$ where $H$ is the union of all 2-blocks
for which the labelling $m_{i}(B_{t})$ is already set’. Clearly, identifying
such $B$ can be done in linear time. The same applies to working through the
cases for defining the various values of $m_{i}(B)$.

Summarizing, it follows that both algorithms run in polynomial time. We note
however, that these algorithms can only decide the existence or potential non-
existence of hamiltonian cycles or hamiltonian paths in the square of graphs
under consideration; they do not construct any such cycle or path.

##  3 Conclusion

The main results of this paper are Theorem 1 and Theorem 2. As we mention in
Introduction Fleischner in [7] proved that in the square of graphs
hamiltonicity and vertex-pancyclicity are equivalent concepts, and so are
hamiltonian connectedness and panconnectedness. Hence we proved in fact that
for graphs satisfying assumptions of Theorem 1, Theorem 2 the square of these
graphs is vertex-pancyclic, panconnected, respectively.

As an easy corollary of Theorem 2 we get the following result.

######  Corollary 8.

Let $G$ be a block-chain. Then $G^{2}$ is panconnected if and only if every
innerblock of $G$ is a 2-block.

Moreover Corollary 8 is also the answer to Problem 1 stated by Chia et al. in
[11] that for a graph $G$ with only two cutvertices it is true that $G^{2}$ is
panconnected if and only if the unique block containing the two cutvertices is
not the complete graph on two vertices.

Acknowledgements. 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.

The first author was partly supported by project GA20-09525S of the Czech
Science Foundation. The second author was supported in part by FWF grant
P27615.

## References

  * [1] S. Alstrup, A. Georgakopoulos, E. Rotenberg, C. Thomassen; A Hamiltonian cycle in the square of a 2-connected graph in linear time; Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1645–1649, SIAM, Philadelphia, PA, 2018.
  * [2] J.A. Bondy, U.S.R. Murty; Graph Theory, Graduate Texts in Mathematics 244; Springer, New York 2008.
  * [3] G. L. Chia, J. Ekstein, H. Fleischner; Revisiting the Hamiltonian Theme in the Square of a Block: The Case of DT-graphs; Journal of Combinatorics 9 (2018), no.1, 119–161.
  * [4] J. Ekstein, H. Fleischner; A Best Possible Result for the Square of a 2-Block to be Hamiltonian; Discrete Mathematics 344 (1) (2021), 112158.
  * [5] H. Fleischner; On Spanning Subgraphs of a Connected Bridgeless Graph and Their Application to DT-Graphs; Journal of Combinatorial Theory 16, No. 1 (1974), 17-28.
  * [6] H. Fleischner; The Square of Every Two-Connected Graph is Hamiltonian; Journal of Combinatorial Theory 16, No. 1 (1974), 29-34.
  * [7] H. Fleischner; In the square of graphs, Hamiltonicity and pancyclicity, hamiltonian connectedness and panconnectedness are equivalent concepts; Monatsh. Math. 82 (1976), 125–149.
  * [8] H. Fleischner, G. L. Chia; Revisiting the Hamiltonian Theme in the Square of a Block: The General Case; Journal of Combinatorics 10 (2019), no.1, 163–201.
  * [9] H. Fleischner, A.M. Hobbs; Hamiltonian total graphs; Mathematische Nachrichten 68 (1975), 59-82.
  * [10] A. Georgakopoulos; A Short Proof of Fleischner’s Theorem; Discrete Mathematics 309 (2009), no. 23-24, 6632-6634.
  * [11] G. L. Chia, S.-H. Ong, L. Y. Tan; On graphs whose square have strong hamiltonian properties; Discrete Mathematics 309 (13) (2009), 4608-4613.
  * [12] J. Müttel, D. Rautenbach; A short proof of the versatile version of Fleischner’s theorem; Discrete Mathematics 313 (2013), no. 19, 1929–1933.
  * [13] S. Říha; A New Proof of the Theorem by Fleischner; Journal of Combinatorial Theory Series B 52 (1991) 117-123.