# Towards a conceptual model for the FAIR Digital Object Framework

Luiz Olavo Bonino da Silva Santos Corresponding Author: Luiz Olavo Bonino da
Silva Santos<EMAIL_ADDRESS>Tiago Prince Sales
Claudenir M. Fonseca  Giancarlo Guizzardi  Semantics, Cybersecurity  &
Services (SCS), University of Twente, The Netherlands  Biosemantics group,
Leiden University Medical Center, The Netherlands

###### Abstract

The FAIR principles define a number of expected behaviours for the data and
services ecosystem with the goal of improving the findability, accessibility,
interoperability, and reusability of digital objects. A key aspiration of the
principles is that they would lead to a scenario where autonomous
computational agents are capable of performing a “self-guided exploration of
the global data ecosystem,” and act properly with the encountered variety of
types, formats, access mechanisms and protocols. The lack of support for some
of these expected behaviours by current information infrastructures such as
the internet and the World Wide Web motivated the emergence, in the last
years, of initiatives such as the FAIR Digital Objects (FDOs) movement. This
movement aims at an infrastructure where digital objects can be exposed and
explored according to the FAIR principles. In this paper, we report the
current status of the work towards an ontology-driven conceptual model for
FAIR Digital Objects. The conceptual model covers aspects of digital objects
that are relevant to the FAIR principles such as the distinction between
metadata and the digital object it describes, the classification of digital
objects in terms of both their informational value and their computational
representation format, and the relation between different types of FAIR
Digital Objects.

###### keywords:

FAIRontology-driven conceptual modellingFAIR Digital Objectsinteroperability

, , and

##  1 Introduction

The evolution of the informatics infrastructure has happened so far in
incremental and complementary steps. Whenever the challenges presented in one
step are addressed, a new set of possibilities emerge and, with them, new
challenges. From the challenges of interconnecting computers in a network to
interconnecting different networks (the internet) and interlinking networked
resources (the World Wide Web), one new layer of interoperability facilitation
leverages from the previous one.

In the digital realm, we constantly interact with different types of entities,
or objects. The totality of bits in a computer’s storage medium is divided
into different units, representing different types of objects and
distinguished based on their different informational value. For instance, the
bits sequence representing a text document, which contains an essay
constitutes a different informational unit than another bits sequence
representing the text editor software.

The FAIR principles [1] brought a vision of a global ecosystem of dynamically
interoperable objects, such as data, services and computing capacity. This
vision includes computational agents that are “ _capable of autonomously and
appropriately acting when faced with the wide range of types, format, and
access mechanisms/protocols that will be encountered in their self-guided
exploration of the global ecosystem_ ”.

This envisioned scenario requires that the exploring computational agents are
provided with enough actionable information about the encountered objects so
that they can automate as much as possible the object’s discovery, access,
interoperation and reuse. The provision of information about digital objects
entails not only that the information is made available to the agents, but it
is also required that the infrastructure, participating systems and services
expose a number of behaviours for the interactions involved in this provision
to be supported. Therefore, to fully realise that vision, we need an
infrastructure capable of supporting the manipulation of digital objects
according to the requirements defined by the FAIR principles as well as
definitions of the expected behaviours of the participating systems,
applications and services.

These challenges to apply the FAIR principles in the current digital
communication infrastructure are the main motivators of the work on the FAIR
Digital Object Framework (FDOF). The FDOF is a framework designed to support
the presentation of informational objects in a digital environment. As the
name suggests, the FDOF is inspired by the notion of Digital Objects
introduced in [2] and extended it to comply with the additional requirements
derived from the FAIR principles.

The FDOF aims at defining features to provide infrastructural support for the
FAIR principles. This set of features added to the underlying communication
infrastructure is concentrated in requirements for a predictable identifier
resolution behaviour, a retrieval mechanism for object metadata from the
object’s identifier and an object typing system.

To define the entities and relations included in the framework we have defined
an ontology-based conceptual model named FAIR Digital Object Framework
Conceptual Model (FDOF-CM), which is the focus of this paper. The remainder of
the paper is organised as follows: Section 2 introduces the FAIR Digital
Object Framework and discusses the ontological foundations used in our
proposed conceptual model; Section 3 presents the FDOF Conceptual Model
detailing its main entities and relations; Section 4 evaluates the FDOF-CM by
deriving an OWL ontology which is validated in a set of relevant use cases;
Section 5 discusses our related work; and Section 6 presents final
considerations and future work.

##  2 Research Baseline

The focus of this paper is the conceptual model defining and describing the
entities and relations present in the FAIR Digital Object Framework. Below we
provide a research baseline of the work on the FDOF and the ontological
notions used in the FDOF-CM.

###  2.1 FAIR Digital Object Framework

In an increasingly complex digital environment automation becomes a necessity
and to support increasing levels of automation, proper identification, and
classification of different digital objects become relevant as well as the
qualification of the relations between them. This brings additional
requirements to the digital ecosystem, which are not properly covered by the
internet or the World Wide Web. The latter, for instance, is based on a
network of digital objects linked through unqualified links, the web links,
i.e., the links between web resources are not semantically defined.

In the seminal paper where the FAIR principles have been introduced [1], the
authors list enabling capabilities that autonomously-acting computational data
exploring agents acquire from information provided by the underlying
infrastructure when facing newly discovered digital objects. These
capabilities are: _“(1) identify the type of object (with respect to both
structure and intent), (2) determine if it is useful within the context of the
agent’s current task by interrogating metadata and/or data elements, (3)
determine if it is usable, with respect to license, consent, or other
accessibility or use constraints, and (4) take appropriate action, in much the
same manner that a human would.”_

These required capabilities can be converted into the following questions that
the framework should support and enable both computational agents and humans
to answer: (Q1) What type of object does this encountered identifier
identifies? (Q2) How can I get more information (e.g., metadata) about this
object? (Q3) How can this object be manipulated, by whom, and under which
conditions?

Given their different nature, digital objects can be manipulated in different
ways. The manipulation of digital objects occurs in a combination of
computational agents and the underlying technological infrastructure. The
interactions happen considering at least two aspects of the digital objects,
their representation or materialisation format and their informational
content. The former distinguishes ways of manipulating different
materialisation formats such as an executable program, a PDF file, or a video
file. While the executable program can be run on a given operating system, we
can “open” the PDF file for reading or editing using specific supporting
software and we can play the video file to watch the animated sequence also
using a video player software. In other words, the possibility of interacting
with a given digital object depends on the ability of the computational agent
or technological infrastructure to handle the object’s encoding format.

The informational aspect of the digital objects is dealt with by inspecting
the content of the bit sequences considering their different informational
roles, e.g., does a given bit sequence represent a structured dataset, a
software code, a natural language text document, or images? Many
materialisation formats are directly related to specific informational roles
such as the MP4 format associated with video sequences and the XML format
related to structured data. But in other cases, this relation is not so clear.
For instance, we can materialise digital images, text, and structured data
using PDF files. In these cases, knowing the materialisation format is not
enough to clarify the informational nature of the digital object. If we want
to increase the autonomy of computational agents in their handling of digital
objects, we should also provide information about each object’s informational
value besides its materialisation format.

In order to support these questions and challenges the FDOF should rely on a
set of clear and unambiguous definitions of the involved concepts and their
relations as well as determine expected behaviours from the underlying
infrastructure and participating computational agents. The proposed conceptual
model discussed in section 3 aims at providing these clear and unambiguous
conceptualizations related to the FDOF. Our focus here is, therefore, the
presentation, description, and discussion of the FDOF conceptual model. For a
more in-depth explanation of the framework itself, its motivation, and
historical evolution, the FDOF documentation [3] should be consulted.

###  2.2 Ontological Foundations

Conceptual models are artefacts developed to provide semantic clarification of
a subject domain. One approach to building conceptual models is to employ
foundational ontologies that assist the modeller in consistently representing
fundamental aspects of the domain. We refer to this approach as ontology-
driven conceptual modelling (ODCM) [4]. We use in this paper an ODCM extension
of UML called OntoUML. OntoUML enriches UML’s class diagram language with
constructs (e.g., classes and relations) that reflect the ontological
categories of the Unified Foundational Ontology (UFO) [5]. Additionally,
OntoUML defines semantically-motivated syntactical constraints designed to
ensure that valid models represent sound UFO ontologies.

OntoUML uses special labels called stereotypes to decorate classes and
relations that express certain ontological categories from UFO. The
stereotyped classes, hereby referred to as types, reflect two orthogonal
classifications criteria from UFO: (i) classifications based on the
ontological nature of the type’s instances (e.g., objects, individualized
properties, abstract values); and (ii) classifications based on modal
characteristics of how the type applies to its instances (e.g., necessarily or
accidentally). We now summarize the stereotypes later employed in Section 3.

The UFO ontology employs the notion of identity principle to refer to the
best-suited criteria to necessarily classify the different sorts of concrete
individuals in a domain. For example, a modeller could select the type
Organization as the type providing the identity principle of its instances
within a taxonomy ranging from Entity to Professional Limited Liability
Organization. In OntoUML, these ultimate sortals (also known as kinds) are
represented by a set of stereotypes that identify both identity principle and
the ontological nature of their instances. The stereotype «kind» identifies
ultimate sortals whose instances are objects in the domain (e.g.,
Organization, Person, Car), while «relator» identifies ultimate sortals whose
instances are individualized relational properties (e.g., Marriage,
Employment, Enrollment). The stereotype «mediation» decorates the associations
between these types of relational properties and the types of objects on which
their instances are existentially dependent (i.e., their _bearers_).

While ultimate sortals uniquely and necessarily classify the entities
following the identity principle it provides, other types of concrete
individuals either classify individuals following a common principle or
classify individuals of a variety of principles. Classes decorated by
«subkind» or «role» inherit a principle provided by an ultimate sortal, where
the former necessarily classifies its instances (e.g., Limited Liability
Organization, Sports Car), and the latter does so accidentally based on some
relational property (e.g., Hired Organization, Rented Car). Classes decorated
with «category» or «roleMixin» are similar to subkinds and roles in
classifying instances either necessarily (e.g., Agent, Vehicle) or
accidentally (e.g., Acting Agent, Damaged Vehicle), but these classify
concrete individuals following different identity principles, i.e., instances
of multiple kinds.

Types decorated by «referenceStrucutre» and «referenceRegion» [6] classify
abstract individuals representing structured conceptual spaces (e.g., the
three-dimensional Colour Space) and individualized regions within these spaces
(e.g., the Colour Value Crimson-H348°-S91%-B86%) respectively. Types decorated
by «type» are higher-order types whose instances are themselves other types
that are part of the subject domain [7], thus, allowing modellers to describe
them and their (higher-order) properties much in the same way one describes
regular individuals. Associations decorated with «instantiation» reify the
notion of instantiation in the model connecting these higher-order types to
their so-called base types, i.e., the super types of their instances,
providing information about the characteristics their instances must inherit
and forming the powertype pattern. Furthermore, associations decorated with
«historicalDependence» indicate historical dependencies of instances of the
association’s target on instances of the source (e.g., in the case of creation
relations). Finally, the relation of redefinition of association ends from UML
has also been employed in Section 3. This allows the modeller to bind
association ends connected to specialised types, to the association ends
connected to their parents, expressing a refinement of their parents’
association with additional constraints.

To facilitate the readability of the ontological natures captured in OntoUML
classes’ tagged values, we use a colour coding to denote the ontological
nature of their instances, with red denoting objects, green denoting
relational properties, purple denoting types, and white denoting abstracts.

##  3 The FAIR Digital Object Framework Conceptual Model

The goals of the FAIR Digital Object Framework Conceptual Model are to define
the main concepts of the framework and how they relate, and to provide the
basis for an ontology of these concepts and relations. This ontology should be
used to semantically annotate the elements of the framework in metadata
records, semantic data and metadata models, or whenever the representation
language used in the digital object allows the inclusion of semantic
annotations, e.g., RDF, OWL.

To facilitate understanding, we have divided the FDOF-CM into three parts:
object identification, basic typing system, and the distinction between
metadata and the object it describes.

###  3.1 FDO Identification

Proper identification of different digital objects is a central point in the
FAIR principles. Three principles explicitly mention identifier, namely: _“F1.
(meta)data are assigned a globally unique and persistent identifier”_ , F3
(_“metadata clearly include the identifier of the data it describes”_) and A1
(_“(meta)data are retrievable by their identifier using a standardized
communication protocol”_).

Figure 1 presents a fragment of the FDOF Conceptual Model where a FAIR Digital
Object is defined as a specialisation of Identified Object. However,
differently from an Identified Object that is generically identified by an
Identifier, FDOs are identified by an specialisation of Identifier that is
globally unique, persistent and resolvable (GUPRI). The refinement from
Identified Object to FAIR Digital Object and from Identifier to GUPRI is a
consequence of the requirements of the FAIR principles F1 (for the globally
uniqueness and persistence) and A1 (for being resolvable) that a FAIR Digital
Object not only needs to be identified by an identifier but this identifier
must guarantee global uniqueness (single reference), persistence (rigid
designation) and be resolvable (retrievable from its identifier).

Figure 1: FDOF - Identification and attribution

The model in Figure 1 defines that Identifiers are Property Values within a
specialisation of Property Value Space named Identification Space. The
Identification Space represents all possible values (identifiers) of that
identification system. One example is that the identification space for
Unified Resource Identifiers (URIs) is the set of possible values for URIs as
defined in [8] following the pattern of a scheme, a colon (:), a single or
double forward slash (/ or //), an authority, a path, a query and a fragment.

Another aspect covered in this FDOF-CM identification fragment is the
reification of the Identification relation between Identifiers and Identified
Objects, and more specifically the FAIR Identification relation between GUPRIs
and FDOs, that are made by Agents. In this way, we can capture the information
of who assigned an identifier to a given FDO, adding to the object’s
provenance.

###  3.2 FDOF Basic Typing System

Types are taken here to be aggregations of properties that are used to
characterise their members. Commonly, the choice is made to fulfil a
particular goal or use. In the realm of digital objects, different typing
systems have been used for different purposes, mainly related to creating
abstractions for the sets of bits stored in computer memory. For instance,
most operating systems use the abstraction of files to organise groups of bits
whereas data sets, potentially spanning over several files or as the content
of database management systems, are commonly used in data science activities.

On the internet, types of digital objects are often associated with Media
Types (formerly known as MIME types) [9]. By looking at the hundreds of types
defined by the Internet Assigned Numbers Authority (IANA) as Media Types, one
cannot avoid noticing some inconsistency in the classification criteria when
taking into consideration the nature of the defined entities. In some cases,
the media type represents a given file encoding format, e.g.,
_application/dicom_ , _audio/mpeg_ , _image/png_ or _video/h264_. In other
cases, the media type represents not only a generic encoding format but how
the content is organised in a particular structure, e.g., the IANA media type
_application/alto-directory+json_ defines both the encoding format (_JSON_)
and a specific structure of key-value pairs following the Application-Layer
Traffic Optimization (ALTO) protocol.

We consider that this typing system based only on the encoding format is
insufficient to support the levels of automation envisioned by the FAIR
principles. For instance, when trying to classify a given photo as an FDO,
should the type of the FDO represent the image captured in the photo, the
encoding format of the photo file or what is depicted in the photo? We argue
that we should consider these three aspects as part of the characterisation of
a given FDO, namely, _(i)_ the encoding format, _(ii)_ the type of the object
regarding its informational content and _(iii)_ the entity(ies) represented by
the object. The motivation for the argument is that a computational agent
benefits from information in these three levels of abstraction to improve its
machine-actionability as required by the FAIR principles. The encoding format
helps determine how the digital object can be processed by the computing
infrastructure (e.g., which parser or reader should be used). The type of the
object considering its informational content helps differentiate, for
instance, images from text, video, applications, etc. Finally, the reference
to the entities represented by the object provides more information about what
the object represents.

Fig. 2 depicts a fragment of the FDOF-CM containing the main classes of the
FDOF basic typing system. In this model, a FAIR Digital Object can be either a
FAIR Digital Information Object (FDIO) or a FAIR Digital Media Object (FDMO).
The FDIO class represents FDOs as units of information. As shown in this
model, Information Object defines a kind, which principle of identity is
defined by the identity of information content. Every FDIO is an Information
Object materialized by at least one FDMO. The FDMO is bit sequence111The kind
Bit Sequence in Fig. 3 defines a self-evident principle of identity inherited
by FDMOs., which (as all Media Objects) encodes characteristics that are
proper to the media type (representing here by Encoding Format). Every FDMO
encodes the information content of a FDIO. In the photo example, John’s
birthday party photo (an instance of FDIO) is materialised by an object named
_JohnBDayPhoto1.jpg_ , which is an instance of FDMO and has the encoding
format _image/jpg_ (instance of Encoding Format). We could also have the same
FDIO materialised by another DFMO instance named _JohnBDayPhoto2.heic_ with
the encoding format _image/heic_. In this example, we have three FDOs
involved, one FAIR Digital Information Object, John’s birthday party photo,
and two FAIR Digital Media Objects, JohnBDayPhoto1.jpg and
JohnBDayPhoto2.heic.

Figure 2: FDOF - FAIR Characterisation

In general, a given FDO is characterised by one sub-type of FAIR Digital
Object Type (FIOT). FIOTs aggregate the set of properties that characterise
information objects of that type (see isAssociatedWith relation in Fig. 2) .
For instance, if we have the photo of John’s birthday party, we can classify
this object as a FDIO having the information object type _Photo_. This _Photo_
FIOT aggregates a number of properties that characterise photos, e.g., the
event depicts, the participants, location, date and time, etc. However, as any
Object here, this photo can have a number of attributions referring to other
Identified Objects (e.g., an attribution participant can point to an
Identified Object of the object type Person, an attribution location can point
to a property value in a geo-coordinate space).

###  3.3 Metadata

One important element of the FAIR principles is the role attributed to
metadata as responsible for describing a given object (principle F2). Many of
the FAIR principles indicate that they apply to both metadata and other types
of objects (principles F1, F4, A1, I1, I2, I3, R1.1, R1.2 and R1.3). Because
of this, the FDOF-CM defines the FAIR Metadata Record (FMR) as a
specialisation of FAIR Digital Information Object with the role of describing
FAIR Digital Objects, as depicted in Fig. 3.

Figure 3: FDOF - Metadata Core

According to our model, the FMR also specialises Dataset, which aggregates
Data Items. In this way, a FMR is a sort of dataset information object which
contains a number of data items representing the attributions of values to
properties that are used to describe a particular object. As an specialisation
of FDIO, the FMR is characterised by a FAIR Information Object Type. The FDOF-
CM supports the possibility of defining specialisations of FAIR Information
Object Type that associate the sets of properties that can (optional) or
should (mandatory) be used to characterise the metadata record. In an
implementation, these definitions can be realised in terms of metadata schemas
associated with given types of FDOs.

The class FDO is abstract (in the UML sense), i.e., cannot be directly
instantiated. Instances of FDO must be either instantiate FAIR Digital
Information Object or FAIR Digital Media Object. Consequently, both FDIOs and
FDMOs should be described by metadata records.

However, the requirement that an FDO must be described by a metadata record
and the fact that a FMR is an specialisation of FDO creates the possibility of
an infinite loop of metadata records requiring being described by meta-
metadata records. To avoid this loop and to better reflect the reality, the
FDOF-CM includes the following constraint rule:
$\textsf{FAIRDigitalObject}(x)\land\neg\textsf{FAIRMetadataRecord}(x)\rightarrow\exists
y\,(\textsf{FAIRMetadataRecord}(y)\land\textsf{isMetadataOf}(y,x))$. This rule
redefines the zero-to-many cardinality of the isMetadataOf relation between
FMR and FDO to require at least one metadata record to describe the FDO unless
the FDO is an instance of FMR. With this constraint rule, the model still
allows metadata records to have their own metadata records but do not mandate
it.

As the model fragment depicted in Fig. 3 indicates, we make a distinction
between digital and non-digital objects. This supports the possibility of
having, for instance, FAIR Metadata Records describing physical objects.
However, in this paper, we focus only on digital objects. In fact, in the
FDOF-CM we have generic elements such as Identified Object, Information
Object, Media Object and Metadata Record. But what makes them FAIR? According
to the FDOF, an Identified Object becomes a FDO, regarding identification,
when it is identified by a GUPRI and not any other type of identifier, as
depicted in Fig. 1. Similarly, a generic Metadata Record becomes a FMR when is
assigned with a GUPRI and includes the identifier of the object it describes
(per FAIR principle F3) using the relation isMetadataOf (Fig. 3). Regarding
metadata and characterisation, an object becomes a FDO when it is
characterised by its informational value (using FDIO), its materialisation
format (using FDMO) and is described by a FMR.

###  3.4 Ontological Considerations

The FDOF-CM has been designed with the requirement of making it as simple as
possible, so that it can be understood in a wider context including all
different types of web practitioners. However, it incorporates a number of
ontological ideas and design patterns.

The mechanism of type characterization in Figs. 1 and 2 embeds the elements of
the Four-Category Ontology pattern (found in Foundational Ontologies such as
UFO, DOLCE, GFO and BFO). Here we have: an Object instantiates an Object Type
and is the bearer of a quality that exemplifies a given Quality Type. Types
here are defined as aggregations of Properties (as in hyperintensional type
definitions). Actual quality individuals are represented by Attributions that
connect the bearer (the Object at hand) with a projection of that quality as a
Property Value in a given Property Value Space. This extends the classical
Four-Category Ontology into the so-called Ontological Octagon as proposed by
[10].

The mechanism in Fig, 3 that treats FAIR Metadata Records (FMRs) as FDIOs
allows for the former to instantiate proper FAIR Digital Object Types and
hence be characterized by properties, but also be described by other FMRs,
themselves FDIOs that can instantiate FAIR Digital Object Types characterized
by Properties and described by FMRs, and so forth. This implements a minimum
set of features available in more sophisticated multi-level theories such as
[11].

The relation between Information Objects and Media Objects seem at first to
reflect the relation of generic dependence between content entities, e.g., The
Aleph by J.L.Borges (as a particular content with fictional individuals,
locations and events) and a particular physical copy of that book standing on
my table, i.e., the notions of Information Content Entity and Information
Bearing Entity in the Information Artifact Ontology (IAO) [12]. However,
notice that a Digital Media Object, e.g., the JPEG bit sequence encoding of a
photo taken at John’s 30th birthday (an Digital Information Object) can have
multiple concretisations as Digital Copies, i.e., actual patterns inhering in
John’s laptop, in Mary’s mobile phone, in Paul’s USB stick, etc, i.e., complex
modes [5]. Thus, FDOF-CM decouples encoding/formating entities from their
possible multiple concretisations. In summary, FDIOs are generically dependent
on FDMOs (the materialization relation in 3), which are themselves generically
dependent on FAIR Digital Copies (FDCs). Our notion of Media Object is akin to
the notion of Information Structure Entity in IAO; our notion of FDC is akin
to Information Bearing Entities in IAO. FDCs will be fully developed in future
work.

##  4 FAIR Digital Object Framework Conceptual Model implementation in OWL

While FDOF can be applied to a variety of technology spaces, the Semantic Web
is among the most significant ones, where OWL ontologies are extensively
employed to provide semantic annotation of both data and metadata. The FAIR
Digital Object Framework Ontology222The FDOF implementation in OWL is
available at https://w3id.org/fdof/ontology. (FDOF-OWL), is an OWL
implementation of FDOF-CM. This implementation extends the gUFO ontology [13],
a lightweight implementation of UFO for the semantic web, representing the
Digital Object and FAIR Digital Object (Figs. 1 and 2) taxonomies as
specialisations of gUFO’s classes. In this section, we demonstrate the
realisability of the FDOF-CM by implementing it in OWL and using one of the
real use cases 333The complete version of all use cases used in the validation
of FDOF are available at https://w3id.org/fdof/fois23-paper..

In FDOF-CM, one of the minimal requirements differentiating FDOs from regular
digital objects is the identification by a GUPRI. However, the object
identifiers in OWL are commonly used as IRIs when making statements about
them. To differentiate objects from GUPRIs, allowing us to make statements
about both independently, FDOF-OWL defines two distinct properties. The first,
fdof:gupri, is a datatype property which can be assigned any data value that
represents the subject’s GUPRI. The second, fdof:isIdentifiedBy, is an object
property whose range is an individualized fdof:Identifier object. These two
uses, presented in LABEL:owl:fdof-gupri through a dataset of Amazon’s top-
selling items, allow for independent statements about objects and GUPRIs, the
first supporting coinciding GUPRIs and IRIs, and the second supporting
statements about the GUPRIs themselves.

⬇

1@prefix : <https://w3id.org/fdof/fois23-paper/ex1/> .

2@prefix fdof: <https://w3id.org/fdof/ontology#> .

3@prefix fdoft: <https://w3id.org/fdof/types#> .

4@prefix dct: <http://purl.org/dc/terms/> .

5@prefix dcat: <http://www.w3.org/ns/dcat#> .

6@prefix schema: <https://schema.org/> .

7

8:amazonTop50 fdof:gupri "https://w3id.org/fdof/fois23-paper/amazonTop50" ;

9 fdof:isIdentifiedBy
<https://w3id.org/fdof/fois23-paper/amazonTop50_identifier> .

Listing 1: Identification of FDOs in OWL.

Next, FDOF-CM defines FAIR metadata records as datasets aggregating data items
(Figs. 3 and 1), information objects that record the attribution of values to
digital objects. In the Semantic Web, data items coincide with the statements
(triples) of an RDF/OWL file. To individualise and aggregate these data items,
FDOF-OWL defines no data item concept but instead makes use of RDF’s named
graphs [14]. In LABEL:owl:fdof-named-graph, named graphs allow us to represent
a set of statements about a dcat:Dataset called :amazonTop50, and refer to
this set as :amazonTop50Metadata. Other statements about :amazonTop50 could
exist outside the named graph, but in this manner, we represent those
aggregated in this metadata record, including the fdof:isMetadataOf reference
back to the metadata. Moreover, independent statements can be made about
:amazonTop50Metadata, e.g., a statement about its license as it could also
differ from the license of :amazonTop50.

⬇

1{

2 :amazonTop50Metadata rdf:type fdof:FAIRMetadataRecord ;

3 fdof:gupri "https://w3id.org/fdof/fois23-paper/ex1/amazonTop50Metadata" ;

4 fdof:hasInformationObjectType fdoft:Dataset ;

5 dct:license <https://creativecommons.org/publicdomain/zero/1.0/> .

6}

7

8:amazonTop50Metadata {

9 :amazonTop50Metadata fdof:isMetadataOf :amazonTop50 .

10 :amazonTop50 rdf:type dcat:Dataset, fdof:FAIRDigitalInformationObject ;

11 fdof:gupri "https://w3id.org/fdof/fois23-paper/ex1/amazonTop50" ;

12 fdof:hasInformationObjectType fdoft:DatasetMetadaRecord ;

13 dct:license <https://creativecommons.org/publicdomain/zero/1.0/> ;

14 dct:issued "2020-10-01"^^xsd:date .

15}

Listing 2: Named graphs representing FAIR metadata records.

As described in Fig. 2, FDOF includes a notion of FAIR information object
types used to prescribe the characteristics required of a FAIR information
object in a particular setting. In the context of OWL, these information
object types are defined as subclasses of fdof:FAIRDigitalInformationObject,
and fdof:hasInformationObjectType, a sub-property of rdf:type, is used to
connect the information object to the type characterising it as a FAIR
(enough) FDO. In LABEL:owl:fdof-named-graph, :amazonTop50 and
:amazonTop50Metadata have relations to hypothetical FAIR information object
types fdoft:Dataset and fdoft:DatasetMetadata which could set requirements
beyond having a GUPRI, such as having explicit licensing information through
dct:license statements, and to include the publication date of a dataset
through dct:issued.

Finally, FDOF-OWL includes the object properties fdof:isMaterializedBy and
fdof:hasEncodingFormat, both related to objects of type
fdof:FAIRDigitalMediaObject. The fdof:isMaterializedBy property, connects an
information object to the digital media object where it is materialized, and
the fdof:hasEncodingFormat property connects the digital media object to its
characterising encoding format, much like the characterisation provided by
fdof:hasInformationObjectType to digital information objects as both instruct
consumers on how to process subject digital object. In LABEL:owl:fdof-media-
object we highlight statements about the media objects from our validation
where :amazonTop50 is said to be materialized in a CSV file, while
:amazonTop50Metadata is materialized in the very Trig file where all these
statements were declared.

⬇

1:amazonTop50 rdf:type dcat:Dataset, fdof:FAIRDigitalInformationObject .

2 fdof:isMaterializedBy :amazonTop50Csv .

3

4:amazonTop50Metadata rdf:type fdof:FAIRMetadataRecord ;

5 fdof:isMaterializedBy :amazonTop50MetadataTrig .

6

7:amazonTop50Csv rdf:type dcat:Distribution, fdof:FAIRDigitalMediaObject ;

8 fdof:hasEncodingFormat <https://iana.org/assignments/media-types/text/csv> .

9

10:amazonTop50MetadataTrig rdf:type dcat:Distribution,
fdof:FAIRDigitalMediaObject ;

11 fdof:hasEncodingFormat <https://iana.org/assignments/media-
types/application/trig> .

Listing 3: FAIR Media Objects in OWL.

In Fig. 4 we summarise in a graph notation all digital objects of the dataset
example used to validate the FDOF-CM. The complete case includes a real
dataset, information objects for its metadata and meta-metadata, and
information objects for the media objects materialising them and their own
metadata. To improve the graph’s readability, we also employ a colour coding
of the FDOF types instantiated444Yellow represents FAIR metadata records;
white represents FAIR media objects; blue represents FAIR information objects;
red represents encoding formats (IANA media types in this case); and green
represents domain information object types.. FDOF-OWL has been validated
through the representation of real use cases involving creative works (photos
with multiple materialisations) and ontologies (including both gUFO and FDOF-
OWL itself).

Figure 4: OWL dataset example in FDOF.

##  5 Related Work

As aforementioned, the FDOF has been inspired by the notion of Digital
Objects. In [2] the authors introduce naming conventions to identify and
located digital objects, a service to locate objects from their names and
elements of a digital object access protocol. Two key entities are introduced:
the obvious digital object and a repository. A digital object is defined as an
instance of an abstract data type composed of two elements, data and key-
metadata. The key-metadata includes the object’s identifier and other
information about the object. The paper also introduces the initial expected
behaviours of the Repository Access Protocol (RAP), such as access and deposit
digital objects.

The work on Digital Objects continued over the years, mainly under the scope
of the DONA Foundation [15]. A key result of this work is the Digital Object
Architecture (DOA) [16]. The DOA defines three core components, namely the
identifier/resolution system, the repository system, and the registry system,
as well as two protocols: the Digital Object Interface Protocol (DOIP)[17] and
the Digital Object Identifier Resolution Protocol (DO-IRP)[18]. The
identifier/resolution system uses the DO-IRP to create, update, delete, and
resolve identifiers of digital objects. The repository system is responsible
for supporting the management of digital objects, including the provision of
access to the stored objects through their identifiers. The DOIP is used by
the repository system and allows software applications to interact with
digital objects. The registry system is a specialisation of repository system
which stores the metadata of the digital objects rather than the digital
objects themselves. In recent years, part of the work on DOs has been
conducted in the context of the FAIR Digital Objects Forum [19]. The FDO Forum
aims at providing a community structure to foster the advance in the
specification and application of FAIR Digital Objects. A number of working
groups have been set to address different aspects of FDOs. The work reported
in the paper has been partially presented and tested in the FAIR Digital
Object Semantics Group (FDO-SIG) of the forum.

The major differences between the work on the FDOF and the DO are that the
latter has been designed from the ground up to follow the aspects of the FAIR
principles that can be supported by technological infrastructures and
applications, and the emphasis on semantic clarity by means of the FDOF-CM.

Regarding semantic models to describe digital objects, we relate our work with
other initiatives such as Dublin Core Terms (DCT) [20], the Data Catalog
Vocabulary (DCAT) [21], Schema.org, and the Metadata for Ontology Description
and publication (MOD) [22]. These models provide classes and relations that
are used to represent entities in metadata records and to provide semantic
annotations to data. The FDOF-CM does not aim at replacing them. Instead, as
shown in the examples on Section 4, we reuse concepts from these models.
However, in FDOF-OWL we provide greater expressivity for aggregating
statements into well-defined metadata records, and we lay a foundation for the
definition of more refined types of FAIR digital objects tailored for specific
applications.

##  6 Final Remarks and Future Work

In this paper, we reported the current state of the work on the conceptual
model of the FAIR Digital Object Framework. In particular, we describe how
FAIR Digital Objects are identified, how they can be classified through the
typing system, and how the model follows the FAIR principles also in regard to
metadata.

We demonstrated the utility of the conceptual model in the context of the
Semantic Web by generating an OWL ontology and using this ontology to describe
the objects in representative real use cases. We argue that characterising
objects by their informational value, encoding format, and related entities,
provides valuable information contributing to semantic clarity. We acknowledge
that this approach not only brings these benefits but also requires the
existence of more instances with their consequent properties and relations,
which may increase complexity. However, it is not expected that these
instances, their identifiers and some of their properties would be manually
created. Supporting systems can be implemented to automate this process,
generating automatically these instances, identifying and setting some of
their properties and, thus, making the adoption of the FDOF easier.

In terms of future work, the FDOF-CM and FDOF-OWL, presented in Sections 3 and
4, lay the foundation for the systematic characterisation and representation
of FAIR Digital Objects according to FDOF. First of all, the mechanisms of
representation of information objects, their metadata, and their
materialisations involve a lot of nuances that have been left out of our
scope, and enhancing this coverage also includes support to non-digital
objects, a subject of great relevance. Second, we focused this paper on the
characterisation of FDOs based on the attributions aggregated into FAIR
metadata records, leaving out the characterisation of operation types present
in FDOF. FDOF’s operation types are fundamental to explaining to both human
and software agents how and when to process information objects, in a finer
level of detail than what is possible through their materialisations and
encoding types. For example, in the case of the Digital Object Architecture
and DOIP support the existence of basic and extended operations. While basic
operations define a set of operations that every DOIP service must support,
extended operations allow different services to implement extra operations
that may be offered. Third, we foresee the possibility of employing automated
verification techniques, such as SHACL, for the definition of FAIR Information
Object Types and the verification of their instances. This should guarantee
that these instances sufficiently adhere to the FAIR principles according to
the requirements defined by the application extending FDOF-OWL.

Finally, the work on the FDOF conceptual model occurs in parallel with the
work on the rest of the framework. Reports on the whole framework, on the
definitions of the protocols and expected behaviours of the participant
applications and services, as well as prototypes and demonstrators, are
currently underway.

## References

  * [1] Wilkinson MD, Dumontier M, Aalbersberg IJ, Appleton G, Axton M, Baak A, et al.  The FAIR Guiding Principles for scientific data management and stewardship.  Scientific Data. 2016;3(1):160018.
  * [2] Kahn R, Wilensky R.  A framework for distributed digital object services.  International Journal on Digital Libraries. 2006;6(2):115-23.
  * [3] Bonino da Silva Santos LO. FAIR Digital Object Framework Documentation; 2021.  https://fairdigitalobjectframework.org.
  * [4] Verdonck M, Gailly F, de Cesare S, Poels G.  Ontology-driven conceptual modeling: A systematic literature mapping and review.  Applied Ontology. 2015;10(3-4):197-227.
  * [5] Guizzardi G.  Ontological foundations for structural conceptual models.  Telematica Instituut; 2005.
  * [6] Albuquerque A, Guizzardi G.  An ontological foundation for conceptual modeling datatypes based on semantic reference spaces.  In: Intl. Conf. on Research Challenges in Information Science; 2013. p. 1-12.
  * [7] Fonseca CM, Guizzardi G, Almeida JPA, Sales TP, Porello D.  Incorporating Types of Types in Ontology-Driven Conceptual Modeling.  In: Conceptual Modeling. Springer; 2022. p. 18-34.
  * [8] Berners-Lee T, et al.  Uniform Resource Identifier (URI): Generic Syntax.  RFC Editor; 2005. 66.
  * [9] Media Types; 2021.  Available from: https://www.iana.org/assignments/media-types.
  * [10] Guizzardi G, Wagner G.  Towards a logic of the ontological dodecagon.  From Philosophy to Computational Logic: Festschrift in Honour of David Pearce’s First. 2012;60:25.
  * [11] Fonseca CM, Almeida JPA, Guizzardi G, Carvalho VA.  Multi-level conceptual modeling: Theory, language and application.  Data & Knowledge Engineering. 2021;134:101894.
  * [12] Smith B, Malyuta T, Rudnicki R, Mandrick W, Salmen D, Morosoff P, et al.  IAO-Intel: An Ontology of Information Artifacts in the Intelligence Domain.  In: Semantic Technologies for Intelligence, Defense, and Security; 2013\. .
  * [13] Almeida JPA, Guizzardi G, Falbo RA, Sales TP. gUFO: A lightweight implementation of the Unified Foundational Ontology (UFO); 2019.  http://purl.org/nemo/gufo.
  * [14] Carroll JJ, Bizer C, Hayes P, Stickler P.  Named graphs.  Journal of Web Semantics. 2005;3(4):247-67.
  * [15] DONA Foundation;.  Accessed: 2023-02-11.  https://www.dona.net.
  * [16] Digital Object Architecture;.  Accessed: 2023-02-11.  https://www.dona.net/digitalobjectarchitecture.
  * [17] Kahn RE, et al.  Digital Object Interface Protocol Specification, version 2.0.  DONA Foundation; 2018.
  * [18] Kahn RE, et al.  Digital Object Identifier Resolution Protocol Specification, version 3.0.  DONA Foundation; 2022.
  * [19] FAIR Digital Objects Forum;.  Accessed: 2023-02-11.  https://fairdo.org/.
  * [20] DCMI Usage Board.  DCMI Metadata Terms; 2006.
  * [21] Browning D, Perego A, Winstanley P, Cox S, Albertoni R, Beltran AG.  Data Catalog Vocabulary (DCAT) - Version 2.  W3C; 2020.  Https://www.w3.org/TR/2020/REC-vocab-dcat-2-20200204/.
  * [22] Dutta B, Toulet A, Emonet V, Jonquet C.  New Generation Metadata Vocabulary for Ontology Description and Publication.  In: Metadata and Semantic Research. Springer; 2017. p. 173-85.


# The Sierpiński Domination Number

1Michael A. Henning, 2,3,4Sandi Klavžar,
1,5Elżbieta Kleszcz, and 5Monika Pilśniak

1Department of Mathematics and Applied Mathematics
University of Johannesburg
Auckland Park, 2006 South Africa
e-mail<EMAIL_ADDRESS>

2Faculty of Mathematics and Physics
University of Ljubljana, Slovenia
e-mail<EMAIL_ADDRESS>

3Institute of Mathematics, Physics and Mechanics
Ljubljana, Slovenia

4 Faculty of Natural Sciences and Mathematics
University of Maribor, Slovenia

5AGH University
Department of Discrete Mathematics
al. Mickiewicza 30, 30-059 Krakow, Poland
e-mail: pilsniak<EMAIL_ADDRESS>

###### Abstract

Let $G$ and $H$ be graphs and let $f\colon V(G)\rightarrow V(H)$ be a
function. The Sierpiński product of $G$ and $H$ with respect to $f$, denoted
by $G\otimes_{f}H$, is defined as the graph on the vertex set $V(G)\times
V(H)$, consisting of $|V(G)|$ copies of $H$; for every edge $gg^{\prime}$ of
$G$ there is an edge between copies $gH$ and $g^{\prime}H$ of $H$ associated
with the vertices $g$ and $g^{\prime}$ of $G$, respectively, of the form
$(g,f(g^{\prime}))(g^{\prime},f(g))$. In this paper, we define the Sierpiński
domination number as the minimum of $\gamma(G\otimes_{f}H)$ over all functions
$f\colon V(G)\rightarrow V(H)$. The upper Sierpiński domination number is
defined analogously as the corresponding maximum. After establishing general
upper and lower bounds, we determine the upper Sierpiński domination number of
the Sierpiński product of two cycles, and determine the lower Sierpiński
domination number of the Sierpiński product of two cycles in half of the cases
and in the other half cases restrict it to two values.

Keywords: Sierpiński graph; Sierpiński product; domination number; Sierpiński
domination number
AMS subject classification: 05C69, 05C76

##  1 Introduction

Sierpiński graphs represent a very interesting and widely studied family of
graphs. They were introduced in 1997 in the paper [15], where the primary
motivation for their introduction was the intrinsic link to the Tower of Hanoi
problem, for the latter problem see the book [12]. Intensive research of
Sierpiński graphs led to a review article [11] in which state of the art up to
2017 is summarized and unified approach to Sierpiński-type graph families is
also proposed. Later research on Sierpiński graphs includes [2, 3, 6, 19, 23].

Sierpiński graphs have a fractal structure, the basic graphs of which are
complete graphs. In 2011, Gravier, Kovše, and Parreau [7] introduced a
generalization in such a way that any graph can act as a fundamental graph,
and called the resulting graphs generalized Sierpiński graphs. We refer to the
papers [1, 4, 5, 13, 14, 16, 17, 20, 21, 22, 24] for investigations of
generalized Sierpiński graphs in the last few years.

An interesting generalization of Sierpiński graphs in the other direction has
recently been proposed by Kovič, Pisanski, Zemljič, and Žitnik in [18].
Namely, in the spirit of classical graph products, where the vertex set of a
product graph is the Cartesian product of the vertex sets of the factors, they
introduced the Sierpiński product of graphs as follows. Let $G$ and $H$ be
graphs and let $f\colon V(G)\rightarrow V(H)$ be an arbitrary function. The
Sierpiński product of graphs $G$ and $H$ with respect to $f$, denoted by
$G\otimes_{f}H$, is defined as the graph on the vertex set $V(G)\times V(H)$
with edges of two types:

  * •

_type- $1$ edge_: $(g,h)(g,h^{\prime})$ is an edge of $G\otimes_{f}H$ for
every vertex $g\in V(G)$ and every edge $hh^{\prime}\in E(H)$,

  * •

_type- $2$ edge_: $(g,f(g^{\prime}))(g^{\prime},f(g))$ is an edge of
$G\otimes_{f}H$ for every edge $gg^{\prime}\in E(G)$.

We observe that the edges of type-$1$ induce $n(G)=|V(G)|$ copies of the graph
$H$ in the Sierpiński product $G\otimes_{f}H$. For each vertex $g\in V(G)$, we
let $gH$ be the copy of $H$ corresponding to the vertex $g$. A type-$2$ edge
joins vertices from different copies of $H$ in $G\otimes_{f}H$, and is called
a _connecting edges_ of $G\otimes_{f}H$. A vertex incident with a connecting
edge is called a _connecting vertex_. We observe that two different copies of
$H$ in $G\otimes_{f}H$ are joined by at most one edge. A copy of the graph $H$
corresponding to a vertex of the graph $G$ in the Sierpiński product
$G\otimes_{f}H$ is called an $H$-layer.

Let $G$ and $H$ be graphs and $H^{G}$ be the family of functions from $V(G)$
to $V(H)$. We introduce new types of domination, the Sierpiński domination
number, denoted by $\gamma_{S}(G,H)$, as the minimum over all functions $f$
from $H^{G}$ of the domination number of the Sierpiński product with respect
to $f$, and upper Sierpiński domination number, denoted by $\Gamma_{S}(G,H)$,
as the maximum over all functions $f\in H^{G}$ of domination number of the
Sierpiński product with respect to $f$. That is,

$\gamma_{\rm S}(G,H)\coloneqq\min_{f\in H^{G}}\\{\gamma(G\otimes_{f}H)\\}$

and

$\Gamma_{\rm S}(G,H)\coloneqq\max_{f\in H^{G}}\\{\gamma(G\otimes_{f}H)\\}\,.$

In this paper, we initiate the study of Sierpiński domination in graphs. In
Section 1.1 we present the graph theory notation and terminology we follow. In
Section 2 we discuss general lower and upper bounds on the (upper) Sierpiński
domination number. Our main contribution in this introductory paper is to
determine the upper Sierpiński domination number of the Sierpiński product of
two cycles, and to determine the lower Sierpiński domination number of the
Sierpiński product of two cycles in half of the cases and in the other half
cases restrict it to two values.

###  1.1 Notation and terminology

We generally follow the graph theory notation and terminology in the books [8,
9, 10] on domination in graphs. Specifically, let $G$ be a graph with vertex
set $V(G)$ and edge set $E(G)$, and of order $n(G)=|V(G)|$ and size
$m(G)=|E(G)|$. For a subset $S$ of vertices of a graph $G$, we denote by $G-S$
the graph obtained from $G$ by deleting the vertices in $S$ and all edges
incident with vertices in $S$. If $S=\\{v\\}$, then we simply write $G-v$
rather than $G-\\{v\\}$. The subgraph induced by the set $S$ is denoted by
$G[S]$. We denote the path, cycle and complete graph on $n$ vertices by
$P_{n}$, $C_{n}$, and $K_{n}$, respectively. For $k\geq 1$ an integer, we use
the notation $[k]=\\{1,\ldots,k\\}$ and $[k]_{0}=\\{0,1,\ldots,k\\}$. We
generally label vertices of the considered graphs by elements of $[n]$. In
this case, the mod function over the set $[n]$ is to be understood in a
natural way, more formally, we apply the following operation for $t\geq 1$:
$t\mathrm{\;mod^{*}\;}n=(t-1)\mathrm{\;mod\;}n+1$.

A vertex _dominates_ itself and its neighbors, where two vertices are
neighbors in a graph if they are adjacent. A _dominating set_ of a graph $G$
is a set $S$ of vertices of $G$ such that every vertex in $G$ is dominated by
a vertex in $S$. The _domination number_ , $\gamma(G)$, of $G$ is the minimum
cardinality of a dominating set of $G$. A dominating set of cardinality
$\gamma(G)$ is called a $\gamma$-_set of $G$_. A thorough treatise on
dominating sets can be found in [8, 9].

If $S$ is a set of vertices in a graph $G$, then we will use the notation
$G|S$ to denote that the vertices in the set $S$ are assumed to be dominated
and hence $\gamma(G|S)$ is the minimum number of vertices in the graph $G$
needed to dominate $V(G)\setminus S$. We note that it could be that a vertex
in $S$ is still a member of a such a minimum dominating set no matter that we
do not need to dominate the vertices in $S$ themselves. If $S=\\{x\\}$, then
we simply denote $G|S$ by $G|x$ rather than $G|\\{x\\}$.

##  2 General lower and upper bounds

We present in this section general lower and upper bounds on the (upper)
Sierpiński domination number.

######  Theorem 2.1.

If $G$ and $H$ are graphs, then

$n(G)\gamma(H)-m(G)\leq\gamma_{\rm S}(G,H)\leq\Gamma_{\rm S}(G,H)\leq
n(G)\gamma(H)\,.$

###### Proof.

Let $G\otimes_{f}H$ be an arbitrary Sierpiński product of graphs $G$ and $H$
and let $X$ be a $\gamma$-set of $G\otimes_{f}H$. Assuming for a moment that
all the connecting edges are removed from $G\otimes_{f}H$, we obtain $n(G)$
disjoint copies of $H$ for which we clearly need $n(G)\gamma(H)$ vertices in a
minimum dominating set. Consider now an arbitrary connecting edge
$e=(g,f(g^{\prime}))(g^{\prime},f(g))$ of $G\otimes_{f}H$. If no end-vertex of
$e$ lies in $X$, then clearly $\gamma(G\otimes_{f}H-e)=\gamma(G\otimes_{f}H)$.
Similarly, if both end-vertices of $e$ lie in $X$, then
$\gamma(G\otimes_{f}H-e)=\gamma(G\otimes_{f}H)$. Hence the only situation in
which $e$ has an effect on $\gamma(G\otimes_{f}H)$ is when
$(g,f(g^{\prime}))\in X$ and $(g^{\prime},f(g))\notin X$ (or the other way
around). But in this case, the effect of the presence of the edge $e$ is that
because $(g,f(g^{\prime}))$ dominates one vertex of $g^{\prime}H$, the edge
$e$ might reduce the domination number by $1$. That is, each connecting edge
can drop the domination number of $G\otimes_{f}H$ by at most $1$, which proves
the left inequality. The other two inequalities are clear. ∎

To show that the lower bound of Theorem 2.1 is achieved, we show later in
Theorem 3.8 that for $n\geq 3$ and $k\geq 1$, if we take $G=C_{n}$ and
$H=C_{3k+1}$ where $n\equiv 0\,({\rm mod\,}\,4)$, then $\gamma_{\rm
S}(G,H)=kn=n(G)\gamma(H)-m(G)$. The upper bound of Theorem 2.1 is obtained,
for example, for the Sierpiński product of two complete graphs. More
generally, to achieve equality in the upper bound of Theorem 2.1 we require
the graph $H$ to have the following property.

######  Theorem 2.2.

The equality in $\Gamma_{\rm S}(G,H)\leq n(G)\gamma(H)$ is achieved if and
only if there exists a vertex $x\in V(H)$ such that $\gamma(H|x)=\gamma(H)$.

###### Proof.

Suppose that $H$ has a vertex $x$ that satisfies $\gamma(H|x)=\gamma(H)$. In
this case, we consider the Sierpiński product $G\otimes_{f}H$ with the
function $f\colon V(G)\rightarrow V(H)$ defined by $f(v)=x$ for every vertex
$v\in V(G)$. Consequently each connecting edge in the product is of the form
$(g,x)(g^{\prime},x)$. Thus, if $X$ is a $\gamma$-set of $G\otimes_{f}H$, then
$|X\cap V(gH)|=\gamma(H)$ because the only vertex of $gH$ that can be
dominated from outside $gH$ is $(g,x)$, but we have assume that
$\gamma(H|x)=\gamma(H)$. Therefore, $\Gamma_{S}(G,H)=n(G)\gamma(H)$.

For the other implication suppose that $\gamma(H|x)<\gamma(H)$ for every
vertex $x\in V(H)$. For an arbitrary edge $g_{1}g_{2}\in E(G)$, if $D$
corresponds to a $\gamma$-set of the product $G\otimes_{f}H$, then $|D\cap
V(G\otimes_{f}H[V(g_{1}H)\cup V(g_{2}H)])|\leq 2\gamma(H)-1$. Consequently,
$\Gamma_{S}(G,H)<n(G)\gamma(H)$. ∎

To conclude this section we describe large classes of graphs for which the
second and the third inequality of Theorem 2.1 are both equality.

######  Proposition 2.3.

If $G$ and $H$ are graphs such that $\Delta(G)<n(H)$ and $\gamma(H)=1$, then
$\Gamma_{\rm S}(G,H)=\gamma_{\rm S}(G,H)=n(G)$.

###### Proof.

Let $G$ and $H$ be graphs such that $\Delta(G)<n(H)$ and $\gamma(H)=1$. Thus,
by Theorem 2.1, $\gamma_{\rm S}(G,H)\leq\Gamma_{\rm S}(G,H)\leq n(G)$ and it
is straightforward that the Sierpiński product of graphs $G$ and $H$ can be
dominated by taking one dominating vertex from each $H$-layer to the
dominating set. It remains to show that the inequality $\gamma_{\rm
S}(G,H)\geq n(G)$ also holds. Suppose that $\gamma_{\rm S}(G,H)\leq n(G)-1$.
Let $D$ be a dominating set of $G\otimes_{f}H$, where $f$ is such that that
minimizes the domination number. Therefore there is an $H$-layer, denote it by
$H^{\prime}$, of $G\otimes_{f}H$ such that $D\cap V(H^{\prime})=\emptyset$.
Since there are at most $\Delta(G)$ connecting edges incident with vertices
from each $H$-layer and $\Delta(G)<n(H)$,then all the vertices from an
$H$-layer cannot be dominated by the vertices from the neighboring layers.
Therefore we have $D\cap V(H^{\prime\prime})\neq\emptyset$ for each
$H^{\prime\prime}$-layer of $G\otimes_{f}H$. Thus $\gamma_{\rm S}(G,H)\geq
n(G)$ and the result follows. ∎

##  3 The Sierpiński domination number of cycles

Let us recall firstly the domination number of a path and a cycle.

######  Observation 3.1.

For $n\geq 3$,
$\gamma(P_{n})=\gamma(C_{n})=\big{\lceil}\frac{n}{3}\big{\rceil}$.

In this section, we shall prove the following results.

######  Theorem 3.2.

For $n\geq 3$, $k\geq 1$, and $p\in[2]_{0}$,

$\gamma_{\rm
S}(C_{n},C_{3k+p})\in\left\\{\begin{array}[]{ll}\\{kn\\};&\mbox{$p=0$,}\vspace{0.2cm}\\\
\\{kn,kn+1\\};&\mbox{$p=1$,}\vspace{0.2cm}\\\
\\{kn+\left\lfloor\dfrac{n}{2}\right\rfloor,kn+\left\lfloor\dfrac{n}{2}\right\rfloor+1\\};&\mbox{$p=2$.}\end{array}\right.$

Moreover, if $n\equiv 0\mod 4$, then $\gamma_{\rm S}(C_{n},C_{3k+1})=kn$ and
$\gamma_{\rm S}(C_{n},C_{3k+2})=kn+\left\lfloor\dfrac{n}{2}\right\rfloor$.

######  Theorem 3.3.

For $n\geq 3$, $k\geq 1$, and $p\in[2]_{0}$,

$\Gamma_{\rm
S}(C_{n},C_{3k+p})=\left\\{\begin{array}[]{ll}kn;&\mbox{$p=0$,}\vspace{0.2cm}\\\
kn+\left\lceil\dfrac{n}{3}\right\rceil\,;&\mbox{$p=1$,}\vspace{0.2cm}\\\
(k+1)n;&\mbox{$p=2$.}\end{array}\right.$

In order to prove Theorems 3.2 and 3.3, we consider three cases, depending on
the value of $p$.

###  3.1 The cycle $C_{n}$ and cycles $C_{3k+1}$

To determine $\Gamma_{S}(C_{n},C_{3k+1})$, we prove a slightly more general
result. For this purpose, we define a class of graphs ${\cal H}_{k}$ as
follows.

######  Definition 3.4.

For $k\geq 1$, let ${\cal H}_{k}$ be the class of all graphs $H$ that have the
following properties.

  1. (a)

$\gamma(H)=k+1$ and $\gamma(H-v)=k$ for every vertex $v\in V(H)$.

  2. (b)

If $x,y\in V(H)$, then there exists a $\gamma$-set of $H$ that contains $x$
and $y$, where $x=y$ is allowed.

We show, for example, that for every $k\geq 1$, the cycle $C_{3k+1}$ belongs
to the class ${\cal H}_{k}$.

######  Proposition 3.5.

For $k\geq 1$, the class ${\cal H}_{k}$ of graphs contains the cycle
$C_{3k+1}$.

###### Proof.

For $k\geq 1$, let $H\cong C_{3k+1}$. Since
$\gamma(C_{n})=\gamma(P_{n})=\lceil n/3\rceil$, property (a) in Definition 3.4
holds. To prove that property (b) in Definition 3.4 holds, let $x,y\in V(H)$.
Since $H$ is vertex-transitive, every specified vertex belongs to some
$\gamma$-set of $H$. In particular, if $x=y$, then property (b) is immediate.
Hence, we may assume that $x\neq y$. Let $H$ be the cycle $v_{1}v_{2}\ldots
v_{3k+1}v_{1}$, where renaming vertices if necessary, we may assume that
$x=v_{1}$. Let $y=v_{i}$, and so $i\in[3k+1]\setminus\\{1\\}$.

Let $H^{\prime}=H-N[\\{x,y\\}]$, that is, $H^{\prime}$ is obtained from $H$ by
removing $x$ and $y$, and removing all neighbors of $x$ and $y$. If
$H^{\prime}$ is connected, then $H^{\prime}$ is a path $P_{3(k-2)+j}$ for some
$j$ where $j\in[3]$. In this case, $\gamma(H^{\prime})=k-1$. If $H^{\prime}$
is disconnected, then $H^{\prime}$ is the disjoint union of two paths
$P_{k_{1}}$ and $P_{k_{2}}$, where $k_{1}+k_{2}=3(k-2)+1$. Thus renaming
$k_{1}$ and $k_{2}$ if necessary, we may assume that either $k_{1}=3j_{1}$ and
$k_{2}=3j_{2}+1$ where $j_{1}\geq 1$, $j_{2}\geq 0$, and $j_{1}+j_{2}=k-2$ or
$k_{1}=3j_{1}+2$ and $k_{2}=3j_{2}+2$ where $j_{1},j_{2}\geq 0$ and
$j_{1}+j_{2}=k-3$. In both cases, $\gamma(H^{\prime})=\lceil
k_{1}/3\rceil+\lceil k_{2}/3\rceil=k-1$. Letting $D^{\prime}$ be a
$\gamma$-set of $H^{\prime}$, the set $D=D^{\prime}\cup\\{x,y\\}$ is a
dominating set of $H$ of cardinality $k+1=\gamma(H)$, implying that $D$ is a
$\gamma$-set of $H$ that contains both $x$ and $y$. Hence, property (b) holds.
∎

For $n\geq 3$ an integer, a _circulant graph_ $C_{n}\langle L\rangle$ with a
given list $L\subseteq\\{1,\ldots,\lfloor\frac{1}{2}n\rfloor\\}$ is a graph on
$n$ vertices in which the $i$th vertex is adjacent to the $(i+j)$th and
$(i-j)$th vertices for each $j$ in the list $L$ and where addition is taken
modulo $n$. For example, for $n=3k+1$ where $k\geq 1$ and $L=\\{1\\}$, the
circulant graph $C_{n}\langle L\rangle$ is the cycle $C_{3k+1}$, which, by
Proposition 3.5, belongs to the class ${\cal H}_{k}$. More generally, for
$n=k(2p+1)+1$ where $k\geq 1$, $p\geq 1$, and $L=[p]$, the circulant graph
$C_{n}\langle L\rangle$ belongs to the class ${\cal H}_{k}$. We omit the
relatively straightforward proof. These examples of circulant graphs serve to
illustrate that for each $k\geq 1$, one can construct infinitely many graphs
in the class ${\cal H}_{k}$. We determine next the upper Sierpiński domination
number $\Gamma_{S}(C_{n},H)$ of a cycle $C_{n}$ and a graph $H$ in the family
${\cal H}_{k}$.

######  Theorem 3.6.

For $n\geq 3$ and $k\geq 1$, if $H\in{\cal H}_{k}$, then

$\Gamma_{\rm S}(C_{n},H)=kn+\left\lceil\dfrac{n}{3}\right\rceil\,.$

###### Proof.

For $n\geq 3$ and $k\geq 1$, let $G\cong C_{n}$ and let $H\in{\cal H}_{k}$.
Let $G$ be the cycle given by $g_{1}g_{2}\ldots g_{n}g_{1}$. In what follows,
we adopt the following notation. For each $i\in[n]$, we denote the copy
$g_{i}H$ of $H$ corresponding to the vertex $g_{i}$ simply by $H_{i}$. We
proceed further with two claims. The first claim establishes a lower bound on
$\Gamma_{\rm S}(C_{n},H)$, and the second claim establishes an upper bound on
$\Gamma_{\rm S}(C_{n},H)$.

######  Claim 1.

$\Gamma_{\rm S}(C_{n},H)\geq kn+\left\lceil\dfrac{n}{3}\right\rceil\,$.

###### Proof.

Let $f\colon V(G)\rightarrow V(H)$ be a constant function, that is, we select
$h\in V(H)$ and for every vertex $g\in V(G)$, we set $f(g)=h$. Let $D_{G}$ be
a $\gamma$-set of $G$. Thus, $|D_{G}|=\gamma(C_{n})=\lceil n/3\rceil$. By
property (a) in Definition 3.4, for every vertex $g\in V(G)$, there exists a
$\gamma$-set of $gH$ that contains the vertex $(g,f(g))=(g,h)$. If $g\in
D_{G}$, let $D_{g}$ be a $\gamma$-set of $gH$ that contains the vertex
$(g,f(g))=(g,h)$, and so $|D_{g}|=\gamma(H)=k+1$. If $g\in V(G)\setminus
D_{G}$, let $D_{g}$ be a $\gamma$-set of $gH-(g,f(g))=gH-(g,h)$, and so in
this case $|D_{g}|=\gamma(H-h)=\gamma(H)-1=k$. Let

$D=\bigcup_{g\in V(G)}D_{g}.$

The set $D$ is a dominating set of $G\otimes_{f}H$, and so

$\gamma(G\otimes_{f}H)\leq|D|=\gamma(G)(k+1)+(n-\gamma(G))k=kn+\gamma(G)=kn+\left\lceil\dfrac{n}{3}\right\rceil\,.$
(1)

For the fixed vertex $h$ chosen earlier, we note that the set of vertices
$(g,h)$ for all $g\in V(G)$ induces a subgraph of $G\otimes_{f}H$ that is
isomorphic to $G\cong C_{n}$. We denote this copy of $G$ by $Gh$. Among all
$\gamma$-sets of $G\otimes_{f}H$, let $D^{*}$ be chosen to contain as many
vertices of $Gh$ as possible. Let $D^{*}_{g}=D^{*}\cap V(gH)$ for every $g\in
V(G)$. Further let $D^{*}_{G}=\\{(g,h)\in D^{*}\colon g\in V(G)\\}$, that is,
$D^{*}_{G}$ is the restriction of $D^{*}$ to the copy of $G$. If a vertex
$(g,h)\notin D^{*}_{G}$ and $(g,h)$ is not dominated by $D^{*}_{G}$, then
$D^{*}_{g}$ is a $\gamma$-set of $gH$ by the minimality of the set $D^{*}$.
However in this case, we could replace the set $D^{*}_{g}$ be a $\gamma$-set
of $gH$ that contains the vertex $(g,h)$ to produce a new $\gamma$-set of
$G\otimes_{f}H$ that contains more vertices from the copy of $G$ than does
$D^{*}$, a contradiction. Hence, the set $D^{*}_{G}$ is a dominating set in
the copy of $G$, and so $|D^{*}_{g}(G)|\geq\gamma(G)$. By the minimality of
the set $D^{*}$ and by property (a) in Definition 3.4, for each vertex $g\in
V(G)$, we have $|D^{*}_{g}|=\gamma(H)=k+1$ if the vertex $(g,h)\in D^{*}_{G}$
and $|D^{*}_{g}|=\gamma(H-h)=k$ if the vertex $(g,h)\notin D^{*}_{G}$.
Therefore,

$\gamma(G\otimes_{f}H)=|D^{*}|=|D^{*}_{G}|(k+1)+(n-|D^{*}_{G}|)k=kn+|D^{*}_{G}|\geq
kn+\gamma(G)=kn+\left\lceil\dfrac{n}{3}\right\rceil\,.$ (2)

By inequalities (1) and (2), we have

$\gamma(G\otimes_{f}H)=kn+\left\lceil\dfrac{n}{3}\right\rceil\,.$ (3)

By equation (3), we have $\Gamma_{\rm
S}(C_{n},H)\geq\gamma(G\otimes_{f}H)=kn+\lceil n/3\rceil\,$. This completes
the proof of Claim 1. ($\Box$)

######  Claim 2.

$\Gamma_{\rm S}(C_{n},H)\leq kn+\left\lceil\dfrac{n}{3}\right\rceil\,$.

###### Proof.

Let $f\colon V(G)\rightarrow V(H)$ be an arbitrary function. Let $H_{i}$ be
the $i$th copy of $H$ corresponding to the vertex $g_{i}$ of $G$ for all
$i\in[n]$. Let $D$ be the dominating set of $G\otimes_{f}H$ constructed as
follows. Let $x_{i}y_{i+1}$ be the connecting edge from $H_{i}$ to $H_{i+1}$
for all $i\in[n]$, where addition is taken modulo $n$. Thus, the vertex
$x_{i}\in V(H_{i})$ is adjacent to the vertex $y_{i+1}\in V(H_{i+1})$ in the
graph $G\otimes_{f}H$, that is, $x_{i}=(g_{i},f(g_{i+1}))$ and
$y_{i+1}=(g_{i+1},f(g_{i}))$. We note that possibly $x_{i}=y_{i}$. By property
(b) in Definition 3.4, there exists a $\gamma$-set of $H_{i}$ that contains
both $x_{i}$ and $y_{i}$. For $i\in[n]$, we define the sets $D_{i,1}$,
$D_{i,2}$, and $D_{i,3}$ as follows. Let $D_{i,1}$ be a $\gamma$-set of
$H_{i}-x_{i}$. Let $D_{i,2}$ be a $\gamma$-set of $H_{i}$ that contains both
$x_{i}$ and $y_{i}$. Let $D_{i,3}$ be a $\gamma$-set of $H_{i}-y_{i}$. We note
that $|D_{i,1}|=|D_{i,3}|=k$ and $|D_{i,2}|=k+1$. For $i\in[n]$, we define the
set $D_{i}$ as follows.

$D_{i}=\left\\{\begin{array}[]{cl}D_{i,1};&\mbox{$i\equiv 1\,({\rm mod\,}\,3)$
and $i\neq n$,}\vspace{0.2cm}\\\ D_{i,2};&\mbox{$i\equiv 2\,({\rm mod\,}\,3)$
or $i\equiv 1\,({\rm mod\,}\,3)$ and $i=n$,}\vspace{0.2cm}\\\
D_{i,3};&\mbox{$i\equiv 0\,({\rm mod\,}\,3)$}.\end{array}\right.$

For example, the set $D_{1}$ dominates all vertices of $H_{1}-x_{1}$. The set
$D_{2}$ contains the vertex $y_{2}$, which is adjacent to the vertex $x_{1}$
of $H_{1}$, and contains the vertex $x_{2}$, which is adjacent to the vertex
$y_{3}$ of $H_{3}$, implying that $D_{2}$ dominates the vertex $x_{1}$ of
$H_{1}$, all vertices of $H_{2}$, and the vertex $y_{3}$ of $H_{3}$. The set
$D_{3}$ dominates all vertices of $H_{3}-y_{3}$. Thus, $D_{1}\cup D_{2}\cup
D_{3}$ dominates all vertices in $V(H_{1})\cup V(H_{2})\cup V(H_{3})$ in the
Sierpiński product $G\otimes_{f}H$. Moreover,
$|D_{1}|+|D_{2}|+|D_{3}|=k+(k+1)+k=3k+1$. More generally, the set
$D_{3j-2}\cup D_{3j-1}\cup D_{3j}$ dominates all vertices in $V(H_{3j-2})\cup
V(H_{3j-1})\cup V(H_{3j})$ in the Sierpiński product $G\otimes_{f}H$ for all
$j\in\\{1,\ldots,\lfloor n/3\rfloor\\}$. Moreover,
$|D_{3j-2}|+|D_{3j-1}|+|D_{3j}|=k+(k+1)+k=3k+1$. If $n\equiv 1\,({\rm
mod\,}\,3)$, then the set $D_{n}$ is a $\gamma$-set of $H_{n}$, and in this
case $|D_{n}|=k+1$. If $n\equiv 2\,({\rm mod\,}\,3)$, then the set
$D_{n-1}\cup D_{n}$ dominates all vertices in $V(H_{n-1})\cup V(H_{n})$, and
in this case $|D_{n-1}|+|D_{n}|=k+(k+1)=2k+1$. The set

$D=\bigcup_{i=1}^{n}D_{i}$

is therefore a dominating set of $G\otimes_{f}H$, implying that

$\gamma(G\otimes_{f}H)\leq|D|=\sum_{i=1}^{n}|D_{i}|=kn+\left\lceil\dfrac{n}{3}\right\rceil\,.$

This completes the proof of Claim 2. ($\Box$)

The proof of Theorem 3.6 follows as an immediate consequence of Claims 1 and
2. ∎

As a consequence of Proposition 3.5, we have the following special case of
Theorem 3.6.

######  Corollary 3.7.

For $n\geq 3$ and $k\geq 1$,

$\Gamma_{\rm S}(C_{n},C_{3k+1})=kn+\left\lceil\dfrac{n}{3}\right\rceil\,.$

We consider next the Sierpiński domination number of $C_{n}$ and $C_{3k+1}$,
and show that $\gamma_{\rm S}(C_{n},C_{3k+1})=kn$ if $n\equiv 0\,({\rm
mod\,}\,4)$ and $\gamma_{\rm S}(C_{n},C_{3k+1})\in\\{kn,kn+1\\}$, otherwise.

######  Theorem 3.8.

For $n\geq 3$ and $k\geq 1$,

$\gamma_{\rm S}(C_{n},C_{3k+1})\in\\{kn,kn+1\\}.$

Moreover, if $n\equiv 0\mod 4$, then $\gamma_{\rm S}(C_{n},C_{3k+1})=kn$.

###### Proof.

For $n\geq 3$ and $k\geq 1$, let $G=C_{n}$ and let $H=C_{3k+1}$. Let $G$ be
the cycle given by $g_{1}g_{2}\ldots g_{n}g_{1}$. We adopt our notation
employed in our earlier proofs. For notational convenience, we let
$V(H)=\\{1,2,\ldots,3k+1\\}$ where vertices $i$ and $i+1$ are consecutive on
the cycle $H$ for all $i\in[3k+1]$ (and where addition is taken modulo $3k+1$,
and so vertex $1$ and vertex $3k+1$ are adjacent).

As before, we denote the copy $g_{i}H$ of $H$ corresponding to the vertex
$g_{i}$ simply by $H_{i}$ for each $i\in[n]$. Thus, $H_{i}=C_{3k+1}$ is the
cycle $(g_{i},1),(g_{i},2),\ldots,(g_{i},3k+1),(g_{i},1)$ for all $i\in[n]$.
Recall that we denote the connecting edge from $H_{i}$ to $H_{i+1}$ by
$x_{i}y_{i+1}$ for all $i\in[n]$, where $x_{i}\in V(H_{i})$, $y_{i+1}\in
V(H_{i+1})$, and addition is taken modulo $n$. Thus,
$y_{i}=(g_{i},f(g_{i-1}))$ and $x_{i}=(g_{i},f(g_{i+1}))$ for all $i\in[n]$.

By Proposition 3.5, the graph $H$ belongs to the class ${\cal H}_{k}$. Thus,
$\gamma(H)=k+1$ and $\gamma(H-v)=k$ for every vertex $v\in V(H)$. Furthermore,
if $x,y\in V(H)$ where $x=y$ is allowed, then there exists a $\gamma$-set of
$H$ that contains $x$ and $y$.

By the elementary lower bound on the Sierpiński domination number given in
Theorem 2.1, $\gamma_{\rm S}(G,H)\geq n(G)\gamma(H)-m(G)=kn$, noting that here
$n(G)=m(G)=n$ and $\gamma(H)=k+1$. It follows that $\gamma_{\rm
S}(C_{n},H)\geq kn$.

To complete the proof we are going to prove that

$\gamma_{\rm S}(C_{n},H)\leq
kn+\left\lceil\dfrac{n}{4}\right\rceil-\left\lfloor\dfrac{n}{4}\right\rfloor\,.$

Let $f\colon V(G)\rightarrow V(H)$ be the function defined by

$f(g_{i})=\left\\{\begin{array}[]{ll}1;&\mbox{$i\bmod
4\in\\{1,2\\}$},\vspace{0.1cm}\\\ 3;&\mbox{otherwise}.\end{array}\right.$

for all $i\in[n]$ where addition is taken modulo $n$. Adopting our earlier
notation, recall that $y_{i}=(g_{i},f(g_{i-1}))$ and
$x_{i}=(g_{i},f(g_{i+1}))$ for all $i\in[n]$. Let $n=4\ell+j$ where
$j\in[3]_{0}=\\{0,1,2,3\\}$. We note that $f(g_{4i-3})=f(g_{4i-2})=1$ and
$f(g_{4i-1})=f(g_{4i})=3$ for all $i\in[\ell]$. Let $D_{i}$ be the unique
$\gamma$-set of $H_{i}-y_{i}\cong P_{3k}$ which consists of all vertices at
distance $2$ modulo $3$ from $y_{i}$ in the graph $H_{i}$ for all $i\in[n]$,
and let

$D=\bigcup_{i=1}^{n}D_{i}.$

We note that $|D_{i}|=k$ for all $i\in[n]$, and so $|D|=kn$. For all
$i\in\\{2,3,\ldots,\ell-1\\}$, the following four properties hold.

  1. (P1): $y_{4i-3}=(g_{4i-3},3)$ and $x_{4i-3}=(g_{4i-3},1)$.

  2. (P2): $y_{4i-2}=(g_{4i-2},1)$ and $x_{4i-2}=(g_{4i-2},3)$.

  3. (P3): $y_{4i-1}=(g_{4i-1},1)$ and $x_{4i-1}=(g_{4i-1},3)$.

  4. (P4): $y_{4i}=(g_{4i},3)$ and $x_{4i}=(g_{4i},1)$.

Hence for all $i\in\\{2,3,\ldots,\ell-1\\}$, the vertices $x_{i}$ and $y_{i}$
are at distance $2$ in $H_{i}$, implying that $x_{i}\in D_{i}$. We consider
four cases to determine which properties hold for the boundary conditions
(that is for $i\in\\{1,\ell\\})$ and finally to set the upper bound on the
domination number in each case.

_Case 1. $n\equiv 0\,({\rm mod\,}\,4)$, that is $n=4\ell$._

In this case, properties P1 and P4 also hold for $i=1$ and $i=\ell$,
respectively. Thus, $y_{1}=(g_{1},3)$ and $x_{1}=(g_{1},1)$, and
$y_{4\ell}=(g_{4\ell},3)$ and $x_{4\ell}=(g_{4\ell},1)$, implying that
$x_{1},x_{4\ell}\in D$. The set $D$ is therefore a dominating set of
$G\otimes_{f}H$, and so $\gamma(G\otimes_{f}H)\leq|D|=kn=kn+\lceil
n/4\rceil-\lfloor n/4\rfloor$.

_Case 2. $n\equiv 1\,({\rm mod\,}\,4)$, that is $n=4\ell+1$._

In this case, $y_{1}=x_{1}=(g_{1},1)$, and $y_{4\ell+1}=(g_{4\ell+1},3)$ and
$x_{4\ell+1}=(g_{4\ell+1},1)$. In particular, property P4 also holds for
$i=\ell$, and so $x_{4\ell+1}\in D$. The set $D\cup\\{x_{1}\\}$ is therefore a
dominating set of $G\otimes_{f}H$, and so
$\gamma(G\otimes_{f}H)\leq|D|+1=kn+1=kn+\lceil n/4\rceil-\lfloor n/4\rfloor$.

_Case 3. $n\equiv 2\,({\rm mod\,}\,4)$, that is $n=4\ell+2$._

In this case, $y_{1}=x_{1}=(g_{1},1)$, and
$y_{4\ell+2}=x_{4\ell+2}=(g_{4\ell+2},1)$. We note that neither $x_{1}$ nor
$x_{4\ell+2}$ belong to the set $D$. The set $D\cup\\{x_{1}\\}$ is a
dominating set of $G\otimes_{f}H$, and so
$\gamma(G\otimes_{f}H)\leq|D|+1=kn+1=kn+\lceil n/4\rceil-\lfloor n/4\rfloor$.

_Case 4. $n\equiv 3\,({\rm mod\,}\,4)$, that is $n=4\ell+3$._

In this case, $y_{1}=(g_{1},3)$ and $x_{1}=(g_{1},1)$, and
$y_{4\ell+3}=x_{4\ell+3}=(g_{4\ell+3},1)$. In particular, property P1 also
holds for $i=1$, and so $x_{1}\in D$. However, $x_{4\ell+3}\notin D$. The set
$D\cup\\{x_{4\ell+3}\\}$ is therefore a dominating set of $G\otimes_{f}H$, and
so $\gamma(G\otimes_{f}H)\leq|D|+1=kn+1=kn+\lceil n/4\rceil-\lfloor
n/4\rfloor$.

In all four cases, $\gamma(G\otimes_{f}H)\leq kn+\lceil n/4\rceil-\lfloor
n/4\rfloor$. ∎

###  3.2 The cycle $C_{n}$ and cycles $C_{3k+2}$

In this section, we determine the Sierpiński domination number
$\gamma_{S}(C_{n},C_{3k+2})$ and the upper Sierpiński domination number
$\Gamma_{S}(C_{n},C_{3k+2})$.

######  Theorem 3.9.

For $n\geq 3$ and $k\geq 1$, we have $\Gamma_{\rm S}(C_{n},C_{3k+2})=(k+1)n$.

###### Proof.

For $n\geq 3$ and $k\geq 1$, let $G\cong C_{n}$ and let $H\cong C_{3k+2}$. Let
$f\colon V(G)\rightarrow V(H)$ be a constant function, that is, we select
$h\in V(H)$ and for every vertex $g\in V(G)$, we set $f(g)=h$. For each vertex
$g\in V(G)$, let $H_{g}$ denote the copy of $H$ associated with the vertex
$g$. Let $D$ be a dominating set of $G\otimes_{f}H$, and let $D_{g}=D\cap
V(H_{g})$, and so $D_{g}$ is the restriction of $D$ to the copy $H_{g}$ of
$H$. If the vertex $(g,h)$ does not belong to $D_{g}$, then $D_{g}$ dominates
all vertices on the path $H_{g}-(g,h)\cong P_{3k+1}$, and so
$|D_{g}|\geq\gamma(P_{3k+1})=k+1$. If the vertex $(g,h)$ does belong to
$D_{g}$, then $D_{g}$ dominates all vertices on the cycle $H_{g}\cong
C_{3k+2}$, and so $|D_{g}|\geq\gamma(C_{3k+2})=k+1$. In both cases,
$|D_{g}|\geq k+1$. Therefore,

$\gamma(G\otimes_{f}H)=|D|=\sum_{g\in V(G)}|D_{g}|\geq(k+1)n,$

implying that $\Gamma_{\rm S}(C_{n},C_{3k+2})\geq(k+1)n$. By the upper bound
in Theorem 2.1, we have $\Gamma_{\rm S}(G,H)\leq n(G)\gamma(H)=(k+1)n$, noting
that in this case $\gamma(H)=\gamma(C_{3k+2})=k+1$. Consequently, $\Gamma_{\rm
S}(C_{n},C_{3k+2})=(k+1)n$. ∎

######  Theorem 3.10.

For $n\geq 3$ and $k\geq 1$,

$\gamma_{\rm
S}(C_{n},C_{3k+2})\in\\{kn+\left\lfloor\dfrac{n}{2}\right\rfloor,kn+\left\lfloor\dfrac{n}{2}\right\rfloor+1\\}.$

Moreover, if $n\equiv 0\mod 4$, then $\gamma_{\rm
S}(C_{n},C_{3k+2})=kn+\left\lfloor\dfrac{n}{2}\right\rfloor$.

###### Proof.

For $n\geq 3$ and $k\geq 1$, let $G\cong C_{n}$ and let $H\cong C_{3k+2}$. We
adopt our notation employed in our earlier proofs. Thus, the cycle $G$ is
given by $g_{1}g_{2}\ldots g_{n}g_{1}$, and $V(H)=\\{1,2,\ldots,3k+2\\}$ where
vertices $i$ and $i+1$ are consecutive on the cycle $H$ for all $i\in[3k+2]$
(and where addition is taken modulo $3k+2$, and so vertex $1$ and vertex
$3k+2$ are adjacent). As before, we denote the copy $g_{i}H$ of $H$
corresponding to the vertex $g_{i}$ simply by $H_{i}$ for each $i\in[n]$.
Thus, $H_{i}=C_{3k+2}$ is the cycle
$(g_{i},1),(g_{i},2),\ldots,(g_{i},3k+2),(g_{i},1)$ for all $i\in[n]$.

We adopt our notation from the proof of Theorem 3.6. Thus, we denote the
connecting edge from $H_{i}$ to $H_{i+1}$ by $x_{i}y_{i+1}$ for all $i\in[n]$,
where $x_{i}\in V(H_{i})$, $y_{i+1}\in V(H_{i+1})$, and addition is taken
modulo $n$. Thus, $y_{i}=(g_{i},f(g_{i-1}))$ and $x_{i}=(g_{i},f(g_{i+1}))$
for all $i\in[n]$.

We proceed further with two claims. The first claim establishes a lower bound
on $\gamma_{\rm S}(G,H)$, and the second claim an upper bound on $\gamma_{\rm
S}(G,H)$. Combining these two bounds yields the desired result in the
statement of the theorem.

######  Claim 3.

$\gamma_{\rm S}(C_{n},H)\geq kn+\left\lfloor\dfrac{n}{2}\right\rfloor$.

###### Proof.

Let $f\colon V(G)\rightarrow V(H)$ be an arbitrary function. We show that

$\gamma(G\otimes_{f}H)\geq kn+\left\lfloor\dfrac{n}{2}\right\rfloor.$ (4)

Let $D$ be a $\gamma$-set of $G\otimes_{f}H$ constructed, and let $D_{i}=D\cap
V(H_{i})$ for $i\in[n]$. If the vertex $x_{i}$ is not dominated by $D_{i}$,
then either $x_{i}\neq y_{i}$, in which case $x_{i}$ is dominated by the
vertex $y_{i+1}\in D$, or $x_{i}=y_{i}$, in which case $x_{i}$ is dominated by
the vertex $x_{i-1}\in D$ or the vertex $y_{i+1}\in D$. Analogously, if the
vertex $y_{i}$ is not dominated by $D_{i}$, then either $x_{i}\neq y_{i}$, in
which case $y_{i}$ is dominated by the vertex $x_{i-1}\in D$, or
$x_{i}=y_{i}$, in which case $y_{i}$ is dominated by the vertex $x_{i-1}\in D$
or the vertex $y_{i+1}\in D$. If a vertex is not dominated by $D_{i}$, then
such a vertex is $x_{i}$ or $y_{i}$, and we say that such a vertex is
dominated from outside $H_{i}$.

Similarly as before, we proceed with a claim that delivers properties of sets
$D_{i}$ leading to the desired lower bound on the Sierpiński domination
number.

######  Claim 3.1.

The following properties hold in the graph $H_{i}$.

  1. (a)

If $d(x_{i},y_{i})\equiv 1\,({\rm mod\,}\,3)$, then $|D_{i}|=k$. Further, both
$x_{i}$ and $y_{i}$ are dominated from outside $H_{i}$.

  2. (b)

If $d(x_{i},y_{i})\not\equiv 1\,({\rm mod\,}\,3)$, then $|D_{i}|=k+1$.

###### Proof.

Suppose that $D_{i}$ contains a vertex $w_{i}$ that dominates $x_{i}$.
Possibly, $w_{i}=x_{i}$. In order to dominate the $3(k-1)+2$ vertices in
$H_{i}$ not dominated by $w_{i}$, at least $k$ additional vertices are needed
even if the vertex $y_{i}$ is dominated outside the cycle $H_{i}$. Thus in
this case, $|D_{i}|\geq k+1$, implying by the minimality of the set $D$ that
$|D_{i}|=k+1$. Analogously, if $D_{i}$ contains a vertex that dominates
$y_{i}$, then $|D_{i}|=k+1$. Hence, if $x_{i}$ or $y_{i}$ (or both $x_{i}$ and
$y_{i}$) are dominated by $D_{i}$, then $|D_{i}|=k+1$.

Suppose that neither $x_{i}$ nor $y_{i}$ is dominated by $D_{i}$, implying
that both $x_{i}$ and $y_{i}$ are dominated from outside the cycle $H_{i}$.
Thus, $D_{i}$ is a dominating set of $H_{i}^{\prime}=H_{i}-x_{i}-y_{i}$. If
$x_{i}=y_{i}$, then $H_{i}^{\prime}=P_{3k+1}$, and by the minimality of $D$ we
have $|D_{i}|=\gamma(P_{3k+1})=k+1$. Hence, we may assume that $x_{i}\neq
y_{i}$. If $x_{i}$ and $y_{i}$ are adjacent, then $H_{i}^{\prime}=P_{3k}$, and
by the minimality of $D$ we have $|D_{i}|=\gamma(P_{3k})=k$. Suppose that
$x_{i}$ and $y_{i}$ are not adjacent, and so $H^{\prime}$ is the disjoint
union of two paths $P_{k_{1}}$ and $P_{k_{2}}$, where $k_{1}+k_{2}=3k$. If
$k_{1}=3j_{1}+1$ and $k_{2}=3j_{2}+2$ (or if $k_{1}=3j_{1}+2$ and
$k_{2}=3j_{2}+1$) for some integers $j_{i}$ and $j_{2}$ where
$j_{1}+j_{2}=k-1$, then $|D_{i}|=\lceil k_{1}/3\rceil+\lceil
k_{2}/3\rceil=(j_{1}+1)+(j_{2}+1)=k+1$. If $k_{1}=3j_{1}$ and $k_{2}=3j_{2}$
where $j_{1}+j_{2}=k$, then $|D_{i}|=\lceil k_{1}/3\rceil+\lceil
k_{2}/3\rceil=j_{1}+j_{2}=k$. Hence if neither $x_{i}$ nor $y_{i}$ is
dominated by $D_{i}$, then either $d(x_{i},y_{i})\equiv 1\,({\rm mod\,}\,3)$,
in which case $|D_{i}|=k$, or $d(x_{i},y_{i})\not\equiv 1\,({\rm mod\,}\,3)$,
in which case $|D_{i}|=k+1$. This proves properties (a) and (b) of the claim.
($\Box$)

By Claim 3.1, if $|D_{i}|=k$ for some $i\in[n]$, then
$|D_{i-1}|=|D_{i+1}|=k+1$ where addition is taken modulo $n$. Furthermore in
this case when $|D_{i}|=k$, the vertices $x_{i}$ and $y_{i}$ are distinct and
are both dominated from outside $H_{i}$, implying that $y_{i+1}\in D_{i+1}$
and $x_{i-1}\in D_{i-1}$. This implies that if $n$ is even, then $|D|\geq
kn+n/2$, and if $n$ is odd, then $|D|\geq kn+(n+1)/2$. This proves inequality
(4).

######  Claim 4.

$\gamma_{\rm S}(C_{n},H)\leq
kn+\left\lfloor\dfrac{n}{2}\right\rfloor+\left\lceil\dfrac{n}{4}\right\rceil-\left\lfloor\dfrac{n}{4}\right\rfloor$.

###### Proof.

Let $f\colon V(G)\rightarrow V(H)$ be the function defined by

$f(g_{i})=\left\\{\begin{array}[]{ll}1;&\mbox{$i\equiv 1\,({\rm
mod\,}\,4)$},\vspace{0.1cm}\\\ 2;&\mbox{$i\equiv 2\,({\rm
mod\,}\,4)$},\vspace{0.1cm}\\\ 3;&\mbox{otherwise}.\end{array}\right.$

for all $i\in[n]$ where addition is taken modulo $n$. Adopting our earlier
notation, recall that $y_{i}=(g_{i},f(g_{i-1}))$ and
$x_{i}=(g_{i},f(g_{i+1}))$ for all $i\in[n]$. Let $n=4\ell+j$ where
$j\in[3]_{0}=\\{0,1,2,3\\}$. We note that $f(g_{4i-3})=1$, $f(g_{4i-2})=2$,
and $f(g_{4i-1})=f(g_{4i})=3$ for all $i\in[\ell]$.

_Case 1. $n\equiv 0\,({\rm mod\,}\,4)$._

Thus, $n=4\ell$. We note that $y_{4i-3}=(g_{4i-3},3)$ and
$x_{4i-3}=(g_{4i-3},2)$ for all $i\in[n]$, and so in the graph $H_{4i-3}$ the
vertices $x_{4i-3}$ and $y_{4i-3}$ are at distance $1$. Moreover,
$y_{4i-1}=(g_{4i-1},2)$ and $x_{4i-1}=(g_{4i-1},3)$ for all $i\in[n]$, and so
in the graph $H_{4i-1}$ the vertices $x_{4i-1}$ and $y_{4i-1}$ are at distance
$1$. This implies that $H_{4i-j}-\\{x_{4i-j},y_{4i-j}\\}\cong C_{3k}$ for
$j\in\\{1,3\\}$. Let $D_{4i-j}$ be a $\gamma$-set of
$H_{4i-j}-\\{x_{4i-j},y_{4i-j}\\}$ for $j\in\\{1,3\\}$, and so $|D_{4i-j}|=k$.

We also note that $y_{4i-2}=(g_{4i-2},1)$ and $x_{4i-2}=(g_{4i-2},3)$ for all
$i\in[n]$, and so in the graph $H_{4i-2}$ the vertices $x_{4i-2}$ and
$y_{4i-2}$ are at distance $2$. Moreover, $y_{4i}=(g_{4i},3)$ and
$x_{4i}=(g_{4i},1)$ for all $i\in[n]$, and so in the graph $H_{4i}$ the
vertices $x_{4i}$ and $y_{4i}$ are at distance $2$. This implies that
$H_{4i-j}-N[\\{x_{4i-j},y_{4i-j}\\}]\cong C_{3(k-1)}$ for $j\in\\{0,2\\}$. Let
$D_{4i-j}$ be a $\gamma$-set of $H_{4i-j}$ that contains both vertices
$x_{4i-j}$ and $y_{4i-j}$ for $j\in\\{0,2\\}$, and so $|D_{4i-j}|=k+1$. The
set

$D=\bigcup_{i=1}^{4\ell}D_{i}$

is a dominating set of $G\otimes_{f}H$, and so
$\gamma(G\otimes_{f}H)\leq|D|=4k\ell+2\ell=kn+n/2$.

_Case 2. $n\equiv 2\,({\rm mod\,}\,4)$._

Thus, $n=4\ell+2$ and in this case, $f(g_{4\ell+1})=1$ and $f(g_{4\ell+2})=2$.
We note that in the graph $H_{4\ell+1}$, the vertices $x_{4\ell+1}$ and
$y_{4\ell+1}$ are at distance $1$ and in the graph $H_{4\ell+2}$ we have
$x_{4\ell+2}=y_{4\ell+2}$. For $i\in[4\ell]$, we define the set $D_{i}$
exactly as in the previous case. Further, let $D_{4\ell+1}$ be a $\gamma$-set
of $H_{4\ell+1}-\\{x_{4\ell+1},y_{4\ell+1}\\}\cong C_{3k}$, and let
$D_{4\ell+2}$ be a $\gamma$-set of $H_{4\ell+2}$ containing $x_{4\ell+2}$. We
note that $|D_{4\ell+1}|=k$ and $|D_{4\ell+2}|=k+1$. The set

$D=\bigcup_{i=1}^{4\ell+2}D_{i}$

is a dominating set of $G\otimes_{f}H$, and so
$\gamma(G\otimes_{f}H)\leq|D|=4k\ell+2k+2\ell+1=kn+n/2$.

_Case 3. $n\equiv 1\,({\rm mod\,}\,4)$._

Thus, $n=4\ell+1$, and in this case, $f(g_{4\ell+1})=1$. Thus,
$y_{4\ell+1}=(g_{4\ell+1},3)$ and $x_{4\ell+1}=(g_{4\ell+1},1)$, and so in the
graph $H_{4\ell+1}$, the vertices $x_{4\ell+1}$ and $y_{4\ell+1}$ are at
distance $2$. For $i\in[4\ell]$, we define the set $D_{i}$ exactly as in the
previous cases. Further, let $D_{4\ell+1}$ be a $\gamma$-set of $H_{4\ell+1}$
that contains the vertex $x_{4\ell+1}$. We note that $|D_{4\ell+1}|=k+1$. The
set

$D=\bigcup_{i=1}^{4\ell+1}D_{i}$

is a dominating set of $G\otimes_{f}H$, and so
$\gamma(G\otimes_{f}H)\leq|D|=4k\ell+k+2\ell+1=kn+(n+1)/2$.

_Case 4. $n\equiv 3\,({\rm mod\,}\,4)$._

Thus, $n=4\ell+3$, and in this case, $f(g_{4\ell+1})=1$, $f(g_{4\ell+2})=2$,
and $f(g_{4\ell+3})=3$. In particular, $y_{4\ell+3}=(g_{4\ell+3},2)$ and
$x_{4\ell+3}=(g_{4\ell+3},1)$, and so in the graph $H_{4\ell+3}$, the vertices
$x_{4\ell+3}$ and $y_{4\ell+3}$ are at distance $1$. For $i\in[4\ell+2]$, we
define the set $D_{i}$ exactly as in Case 2. Further, let $D_{4\ell+3}$ be a
$\gamma$-set of $H_{4\ell+3}$ containing the vertex $x_{4\ell+3}$. We note
that $|D_{4\ell+3}|=k+1$. The set

$D=\bigcup_{i=1}^{4\ell+3}D_{i}$

is a dominating set of $G\otimes_{f}H$, and so
$\gamma(G\otimes_{f}H)\leq|D|=4k\ell+3k+2\ell+2=kn+(n+1)/2$. The desired
result of the claim now follows from the four cases above. ($\Box$)

The proof of Theorem 3.10 follows as an immediate consequence of Claim 3 and
Claim 4. ∎

###  3.3 The cycle $C_{n}$ and cycles $C_{3k}$

In this section, we determine the Sierpiński domination number
$\gamma_{S}(C_{n},C_{3k})$ and the upper Sierpiński domination number
$\Gamma_{S}(C_{n},C_{3k})$.

######  Theorem 3.11.

For $n\geq 3$ and $k\geq 1$,

$\gamma_{\rm S}(C_{n},C_{3k})=\Gamma_{\rm S}(C_{n},C_{3k})=kn.$

###### Proof.

We adopt our notation from the earlier sections. Let $G\cong C_{n}$ be the
cycle $g_{1}g_{2}\ldots g_{n}g_{1}$, and let $H_{i}$ be the $i$th copy of
$C_{3k}$ corresponding to the vertices $g_{i}$ of $G$ for $i\in[n]$. As
before, we denote the connecting edge from $H_{i}$ to $H_{i+1}$ by
$x_{i}y_{i+1}$ for all $i\in[n]$.

Let $f\colon V(G)\rightarrow V(H)$ be an arbitrary function. Let $D$ be a
$\gamma$-set of $G\otimes_{f}H$, and let $D_{i}=D\cap V(H_{i})$ for $i\in[n]$.
We show that $|D_{i}|=k$ for all $i\in[n]$. If both vertices $x_{i}$ and
$y_{i}$ are dominated by $D_{i}$, then $D_{i}$ is a $\gamma$-set of
$H_{i}\cong C_{3k}$, and so $|D_{i}|=k$. If exactly one of $x_{i}$ and $y_{i}$
is dominated by $D_{i}$, say $x_{i}$, then by the minimality of the set $D$,
the set $D_{i}$ is a $\gamma$-set of $H_{i}-y_{i}\cong P_{3k-1}$, and so
$|D_{i}|=k$. Hence, we may assume that neither $x_{i}$ nor $y_{i}$ is
dominated by $D_{i}$, for otherwise, $|D_{i}|=k$ and the desired bound
follows.

With our assumption that neither $x_{i}$ nor $y_{i}$ is dominated by $D_{i}$,
the set $D_{i}$ is a $\gamma$-set of $H_{i}^{\prime}=H_{i}-\\{x_{i},y_{i}\\}$.
If $x_{i}=y_{i}$, then $H_{i}^{\prime}=P_{3k-1}$, and by the minimality of $D$
we have $|D_{i}|=\gamma(P_{3k-1})=k$. Hence, we may assume that $x_{i}\neq
y_{i}$. If $x_{i}$ and $y_{i}$ are adjacent, then $H_{i}^{\prime}=P_{3k-2}$,
and by the minimality of $D$ we have $|D_{i}|=\gamma(P_{3k-2})=k$. Suppose
that $x_{i}$ and $y_{i}$ are not adjacent, and so $H^{\prime}$ is the disjoint
union of two paths $P_{k_{1}}$ and $P_{k_{2}}$, where $k_{1}+k_{2}=3k-2$. If
$k_{1}=3j_{1}+1$ and $k_{2}=3j_{2}$ for some integers $j_{i}$ and $j_{2}$
where $j_{1}+j_{2}=k-1$, then $|D_{i}|=\lceil k_{1}/3\rceil+\lceil
k_{2}/3\rceil=(j_{1}+1)+j_{2}=k$. Analogously, if $k_{1}=3j_{1}$ and
$k_{2}=3j_{2}+1$, then $|D_{i}|=k$. If $k_{1}=3j_{1}+2$ and $k_{2}=3j_{2}+2$
for some integers $j_{i}$ and $j_{2}$ where $j_{1}+j_{2}=k-2$, then
$|D_{i}|=\lceil k_{1}/3\rceil+\lceil k_{2}/3\rceil=(j_{1}+1)+(j_{2}+1)=k$. In
all cases, $|D_{i}|=k$, implying that

$\gamma(G\otimes_{f}H)=|D|=\sum_{i=1}^{n}|D_{i}|=kn.$

Since $f\colon V(G)\rightarrow V(H)$ was chosen as an arbitrary function, and
$D$ as an arbitrary $\gamma$-set of $G\otimes_{f}H$, we deduce that
$\gamma_{\rm S}(C_{n},C_{3k})=\Gamma_{\rm
S}(C_{n},C_{3k})=\gamma(G\otimes_{f}H)=kn$. ∎

## Concluding remarks

It seems to us that in the vast majority of cases where the lower Sierpiński
domination number of the Sierpiński product of two cycles is specified to two
values exactly, the larger of the two is the correct value. However, the
following example, which surprised us, demonstrates that there are also cases
where the exact value is the smaller of the two possible values.

Let $G\cong C_{18}$ with $V(G)=[18]$ and let $H\cong C_{7}$ with $V(H)=[7]$
and let the function $f:V(G)\rightarrow V(H)$ be defined as follows:

$\displaystyle f(1)$ $\displaystyle=f(4)=f(5)=f(18)=4,$ $\displaystyle f(2)$
$\displaystyle=f(3)=f(6)=f(7)=2,$ $\displaystyle f(8)$ $\displaystyle=f(9)=7,$
$\displaystyle f(10)$ $\displaystyle=f(11)=5,$ $\displaystyle f(12)$
$\displaystyle=f(13)=3,$ $\displaystyle f(14)$ $\displaystyle=f(15)=1,$
$\displaystyle f(16)$ $\displaystyle=f(17)=6.$

Then Theorem 3.2 asserts that $\gamma(G\otimes_{f}H)\in\\{36,37\\}$ and it is
straightforward to check that the exact value is $\gamma(G\otimes_{f}H)=36$.

## Acknowledgements

We would like to thank the reviewer very much for careful reading of the paper
and in particular for pointing to a subtle technical detail that led to the
reformulation of one of the main theorems.

This research was obtained during the sabbatical visit of the first author at
the University of Ljubljana and he thanks them for their kindness in hosting
him. The first author also acknowledges that his research visit was supported
in part by the University of Johannesburg and the South African National
Research Foundation. S.K. acknowledges the financial support from the
Slovenian Research Agency (research core funding No. P1-0297 and projects
J1-2452, N1-0285).

## References

  * [1] K. Balakrishnan, M. Changat, A.M. Hinz, D.S. Lekha, The median of Sierpiński graphs, Discrete Appl. Math. 319 (2022) 159–170.
  * [2] B. Brešar, J. Ferme, Packing coloring of Sierpiński-type graphs, Aequationes Math. 92 (2018) 1091–1118.
  * [3] F. Deng, Z. Shao, A. Vesel, On the packing coloring of base-$3$ Sierpiński graphs and $H$-graphs, Aequationes Math. 95 (2021) 329–341.
  * [4] A. Estrada-Moreno, E. D. Rodríguez-Bazan, J. A. Rodríguez-Velázquez, On distances in generalized Sierpiński graphs, Appl. Anal. Discrete Math. 12 (2018) 49–69.
  * [5] A. Estrada-Moreno, J. A. Rodríguez-Velázquez, On the general Randić index of polymeric networks modelled by generalized Sierpiński graphs, Discrete Appl. Math. 263 (2019) 140–151.
  * [6] M. F. D. Ghouchan, E. Ghorbani, H. R. Maimani, F. R. Mahid, Some algebraic properties of Sierpiński-type graphs, Ars Math. Contemp. 20 (2021) 171–186.
  * [7] S. Gravier, M. Kovše, A. Parreau, Generalized Sierpiński graphs, in: Posters at EuroComb’11, Budapest, http://www.renyi.hu/conferences/ec11/posters/parreau.pdf (2017–12–11).
  * [8] T. W. Haynes, S. T. Hedetniemi, M. A. Henning (eds.), Topics in Domination in Graphs, Dev. Math., vol 64. Springer, Cham (2020).
  * [9] T. W. Haynes, S. T. Hedetniemi, M. A. Henning (eds.), Structures of Domination in Graphs, Dev. Math., vol 66. Springer, Cham (2021).
  * [10] M. A. Henning, A. Yeo, Total Domination in Graphs (Springer Monographs in Mathematics) 2013. ISBN: 978-1-4614-6524-9 (Print) 978-1-4614-6525-6 (Online).
  * [11] A. M. Hinz, S. Klavžar, S. S. Zemljič, A survey and classification of Sierpiński-type graphs, Discrete Appl. Math. 217 (2017) 565–600.
  * [12] A. M. Hinz, S. Klavžar, C. Petr, The Tower of Hanoi—Myths and Maths. Second Edition. Birkhäuser/Springer, Cham (2018). xviii + 458 pp. ISBN: 978-3-319-73778-2; 978-3-319-73779-9.
  * [13] W. Imrich, I. Peterin, Recognizing generalized Sierpiński graphs, Appl. Anal. Discrete Math. 14 (2020) 122–137.
  * [14] M. Khatibi, A. Behtoei, F. Attarzadeh, Degree sequence of the generalized Sierpiński graph, Contrib. Discrete Math. 15 (2020) 88–97.
  * [15] S. Klavžar, U. Milutinović, Graphs $S(n,k)$ and a variant of the Tower of Hanoi problem, Czechoslovak Math. J. 47(122) (1997) 95–104.
  * [16] S. Klavžar, S. S. Zemljič, Connectivity and some other properties of generalized Sierpiński graphs, Appl. Anal. Discrete Math. 12 (2018) 401–412.
  * [17] D. Korže, A. Vesel, Packing coloring of generalized Sierpiński graphs, Discrete Math. Theor. Comput. Sci. 21 (2019) No. 3, Paper No. 7.
  * [18] J. Kovič, T. Pisanski, S. S. Zemljič, A Žitnik, The Sierpiński product of graphs, Ars Math. Contemp. 23 (2023) #P1.01.
  * [19] C.-A. Liu, Roman domination and double Roman domination numbers of Sierpiński graphs $S(K_{n},t)$, Bull. Malays. Math. Sci. Soc. 44 (2021) 4043–4058.
  * [20] M.K. Menon, M.R. Chithra, K.S. Savitha, Security in Sierpiński graphs, Discrete Appl. Math. 328 (2023) 10–15.
  * [21] F. Ramezani, E. D. Rodríguez-Bazan, J. A. Rodríguez-Velázquez, On the Roman domination number of generalized Sierpiński graphs, Filomat 31 (2017) 6515–6528.
  * [22] J. A. Rodríguez-Velázquez, E. D. Rodríguez-Bazan, A. Estrada-Moreno, On generalized Sierpiński graphs, Discuss. Math. Graph Theory 37 (2017) 547–560.
  * [23] J. Varghese, S. Aparna Lakshmanan, Italian domination on Mycielskian and Sierpiński graphs, Discrete Math. Algorithms Appl. 13 (2021) 2150037.
  * [24] E. Vatandoost, F. Ramezani, S. Alikhani, On the zero forcing number of generalized Sierpiński graphs, Trans. Comb. (2019) 41–50.