![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
In this paper, we obtain the Italian domination number, perfect Italian domination number and double Roman domination number of generalized Sierpiński graph where G is a cycle Cn,
a complete bipartite graph
or
and a bistar
1. Introduction
Let G be a simple graph with vertex set V(G) and edge set E(G). If there is no ambiguity in the choice of G, then we write V(G) and E(G) as V and E, respectively. The number of vertices and edges of the graph G are denoted by n(G) and m(G), respectively. The open neighbourhood of a vertex is the set
and the vertices in N(v) are called the neighbours of v.
is called the degree of the vertex v in G and is denoted by
or simply d(v). The vertices with degree one are called leaves, whereas the vertices with degree
are called universal vertices. Let Cn denote a cycle on n vertices and
denote a complete bipartite graph on p + q vertices, where one partition contains p vertices and other partition contains q vertices. The bistar
is the graph obtained by joining the center vertices of
and
by an edge.
Let f be a function defined on the vertex set of a graph G. The weight of f is defined as A Roman dominating function on G is a function
such that every vertex
with
has at least a neighbor
satisfying
The Roman domination number of G, denoted by
is the minimum weight among all Roman dominating functions on G. Cockayne, Dreyer, S. M. Hedetniemi and S. T. Hedetniemi [Citation14] introduced the concept of Roman Domination in graphs, and since then a lot of related variations and generalizations have been studied (see [Citation7, Citation11–13]).
An Italian dominating function – IDF (perfect Italian dominating function – PID-function) of a graph G is a function satisfying the condition that for every
with
we have
(
), i.e., either v is adjacent to at least one vertex u with
or at least two vertices x and y with
(i.e., all the neighbours of v are assigned the weight 0 by f except for exactly one vertex u for which
or for exactly two vertices u and w for which
). The Italian domination number,
(perfect Italian domination number,
) is the minimum weight of an Italian dominating function [Citation24] (perfect Italian dominating function [Citation23]). The Italian dominating function with weight
is called a γI-function [Citation10]. The sum of the weights of the vertices of H is denoted by f(H), where H is any subgraph of G. i.e.,
The study of Italian domination was initiated by Chellai et al. in [Citation10] and they called Italian domination as Roman
-domination. Italian domination is fairly a new concept and there are only a handful of papers on Italian domination. Interested readers may refer to [Citation2, Citation17, Citation18, Citation20, Citation22, Citation24, Citation26, Citation28] and [Citation35]. In [Citation29], the exact value of perfect Italian domination number for Cartesian product of some special graphs is obtained. A relation between the Roman domination number and the perfect Italian domination number of a graph G is obtained and the corresponding realization problem is also solved. In [Citation32], the authors characterize the graphs G with
equal to 2 and 3 and determined the exact value of the parameter for several simple-structured graphs. It is also proved that it is NP-complete to decide whether a given bipartite graph admits a perfect Italian dominating function of weight k.
Given a graph a function
having the property that if f(v) = 0, then there exist
such that
or there exists
such that f(w) = 3, and if f(v) = 1, then there exists
such that
is called a double Roman dominating function (DRDF). The double Roman domination number,
is the minimum among the weights of DRDFs on G. If
is a function defined on V(G), then
is denoted by
(If there is no ambiguity,
is written as Vi [Citation9]. The study of double Roman domination was initiated by R. A. Beeler, T. W. Haynes and S. T. Hedetniemi in [Citation9]. Interested readers may refer [Citation3–6, Citation21, Citation34, Citation36] and [Citation38]. Domination parameters in some classes of graphs have been studied by several authors (see [Citation15, Citation16]).
Let be a non-empty graph of order
and t a positive integer. Let Vt be the set of words of length t on alphabet V. A word u of length t is denoted by
The graph
was introduced by Klavžar and Milutinović in [Citation30] and was later called as Sierpiński graphs in [Citation31].
has vertex set Vt and
is an edge if and only if there exists
such that: (i)
if
(ii)
(iii)
and
if
The vertices of the form
are called extreme vertices of
The generalized Sierpiński graph of a graph G, denoted by S(G, t), is a graph with vertex set Vt and edge set [Citation19]. Note that
is G itself. If
is the vertex set of G, then in
induces a copy of G for each
The subgraph induced by Vi is denoted by Gi, for
gives
and
The value of various domination parameters of Sierpiński graphs were studied in [Citation6, Citation27, Citation33] and [Citation37]. The reader may refer to the survey paper [Citation25]. For any graph theoretic terminology and notations not mentioned here, the readers may refer to [Citation8].
The following results are useful in this paper.
Theorem 1.1.
[Citation10] For a cycle Cn and a path Pn,
Theorem 1.2.
[Citation32] For a cycle Cn,
Proposition 1.3.
[Citation9] In a double Roman dominating function of weight , no vertex needs to be assigned the value 1.
Proposition 1.4.
[Citation1] For
Proposition 1.5.
[Citation1] For
In this paper, we obtain the exact values of the Italian domination number, the perfect Italian domination number and the double Roman domination number of the generalized Sierpiński graph where G is a cycle Cn,
a complete bipartite graph
or
and a bistar
2. Main Results
For n = 3, and
and
were discussed in [Citation27, Citation28] and [Citation6], respectively. Hence, in this section, we consider Cn, for
only.
Theorem 2.1.
The Italian domination number of the generalized Sierpiński graph is
, for
Proof.
Let Then
has the vertex set
and edge set
In
there are n copies of Cn and we know that
Therefore, if we take a γI-function in each copy of Cn, we get an IDF of
so that
For the reverse inequality, note that in is the extreme vertex and
and
are the vertices which are adjacent to
and
respectively. The vertices other than
form a path on
vertices, say
Therefore,
To Italian dominate
(which do not have any adjacency outside
) we need minimum weight 2. Therefore,
so that
Hence,
□
Corollary 2.2.
The perfect Italian domination number of the generalized Sierpiński graph is
, for
Proof.
We know that The proof is similar to that of Theorem 2.1. □
Lemma 2.3.
If Pn is a path on n vertices, where n is a multiple of 3, then the weight of a γdR-function assigned to the end vertices is always zero.
Proof.
Let Pn be the path Let f be any γdR-function with
Then v1 cannot double Roman dominate any other vertex. Hence,
so that
which is a contradiction.
Now let f be a γdR-function with If
then none of the vertices of
are double Roman dominated by vertices outside
Consequently,
so that
which is a contradiction. If
then we can find a DRDF g as follows.
and
for
Clearly, g is a DRDF with weight less than that of f, which is also a contradiction. Hence, we conclude that
Similarly, the case when also leads to a contradiction and so
In the same manner, we can also prove that
□
Lemma 2.4.
If Cn is a cycle, where n is an odd multiple of 3 then in any γdR-function, no vertex is assigned the weight 2.
Proof.
Let Cn be a cycle and let f be a γdR-function with at least one vertex assigned the weight 2. For definiteness, let
If
is non-zero, then
and
so that
which is a contradiction. If
then
must be non-zero. If
then
and
so that
which is also a contradiction. Hence,
Continuing this argument, we get
or 2 according as i is even or odd, respectively, so that
which is a contradiction. Hence, the result follows. □
Theorem 2.5.
The double Roman domination number of the generalized Sierpiński graph is
Proof.
Let Then
has the vertex set
and edge set
We consider the following cases.
Case 1: is even.
Define the following function on
Clearly, f is a DRDF and
Hence,
For the reverse inequality, note that in each is the extreme vertex and
and
are the only vertices adjacent to other copies of Cn. The remaining vertices (other than
) form a path on
vertices, say
Let f be any DRDF of
If
then
and
so that
If
then one of
and
must be 2. For definiteness, let
Then
In this case,
so that
If
then one of
and
is 3. For definiteness, let
Then
so that
If
then
so that
Thus, in all cases,
and if
then
and
We claim that if
then
Since
then
by Lemma 2.3. Therefore, since
to double Roman dominate
so that
Thus if
then
so that
Case 2:
is odd.
As in case 1, for any γdR-function f of
for each
We claim that if
then both
and
is at least n. If
then
and
So to double Roman dominate
must be at least 2. If
then
by Lemma 2.4 and so
If
then
must be zero in order to make
i.e., the only vertex which is outside
and double Roman dominated by vertices in
is
Similarly,
and the only vertex which is outside
and double Roman dominated by vertices in
is
Thus, for three consecutive copies of Cn, at most one copy can have weight
and hence
Case 3:
Define the following function on
Clearly, f is a DRDF and
Hence,
For the reverse inequality, note that for all
as in above cases and hence
Case 4:
Define the following function on
Clearly, f is a DRDF and
Hence,
For the reverse inequality, the proof is similar to case 3 except when If
then
and hence
can be considered as a path on
vertices of which none of the vertices are double Roman dominated by vertices from copies of Cn other than
Consequently,
If
then
and so
Thus in all cases,
and hence
□
When p = 1 and q = 1 is K2 and it is proved in [Citation28] that
Therefore,
and also
Also in [Citation6], it is found that
and hence
When p = 1 and q = 2 then
and it is a simple observation that
and
Hence, in the following theorems, we consider the case p = 1 and
Theorem 2.6.
The Italian domination number of the generalized Sierpiński graph is
Proof.
Let be the vertices of
where v1 is the universal vertex. Define the following function on
as follows.
Clearly, f is an IDF and
and hence,
Since each copy of
for
contains three or more leaves. So to Italian dominate these vertices we need to assign weight at least 2 to the vertex
Now in
the vertices
are Italian dominated by
So the only vertex which is not Italian dominated in
is
Hence, we have to assign weight 1 to
so that,
Therefore,
□
Theorem 2.7.
The perfect Italian domination number of the generalized Sierpiński graph is
Proof.
Let be the vertices of
where v1 is the universal vertex. Define the following function on
as follows.
Clearly, f is a PID function and
Therefore,
In each for
there are q vertices which are not adjacent to vertices of other copies of
Hence, for any
-function f of
Also, it is optimum to assign the weight 2 to
where
Now, the only vertex which is not perfect Italian dominated is
We cannot give the weight 1 to
since, in this case
for
Hence, we have to give weight to the vertices of
so that
which results in
Therefore,
Hence,
□
Theorem 2.8.
The double Roman domination number of the generalized Sierpiński graph is
Proof.
The proof is similar to that of Theorem 2.6 with the difference that the weights 2 and 1 are replaced by 3 and 2, respectively. □
When and it is discussed in the section 2.
Theorem 2.9.
The Italian domination number of the generalized Sierpiński graph is
for p = 2,
Proof.
Let be the vertex set of
and
Define the following function on
as follows.
It can be easily verified that f is an IDF and
Therefore,
In each there are at least two vertices which are not adjacent to vertices of other copies of
So to Italian dominate
we need at least weight 2. Therefore,
Hence,
□
Proposition 2.10.
The perfect Italian domination number of generalized Sierpiński graph is
Proof.
Let be the vertex set of
where
and
are the partite sets of the vertex set. Define a function f on
as follows.
It can be easily verified that f is a PID- function and
so that
(This labeling is illustrated in .)
In each copy of there are at least 2 vertices which are not adjacent to the vertices of other copies of
Hence to perfect Italian dominate each
we need minimum weight 2. If possible, assume that
for every
In particular,
Since
and
are not adjacent to any vertices of other copies of
these vertices must be perfect Italian dominated by the vertices of
Then, one of the following cases may arise.
Case 1:
Since Since f is a PID function
and hence
for
Now, to perfect Italian dominate
we must have
This implies, there exists at least one vertex
with
To perfect Italian dominate this
we must have
which is a contradiction to the fact that
Case 2:
Then for the vertices and
either two vertices have weight 1 or one vertex has weight 2.
Subcase(a): Two vertices have weight 1 and the third vertex has weight 0.
For definiteness, let and
Now, to perfect Italian dominate
we must have
Since
To perfect Italian dominate
we must have
Since
To perfect Italian dominate
and
we must have
But the vertices
and
are not perfect Italian dominated. To perfect Italian dominate these vertices we need more weight, which contradicts the fact that
for all i.
Subcase(b): One vertex has weight 2 and other vertices have weight 0.
For definiteness, let and
for
To perfect Italian dominate
and
we must have
Since
we have
To perfect Italian dominate
and
we must have
which is a contradiction to the fact that
Therefore, Hence,
□
Theorem 2.11.
The perfect Italian domination number of the generalized Sierpiński graph is
, for
Proof.
Let be the vertex set of
where
and
are the partite sets of
Define a function on
as follows.
Clearly, f is a PID-function and
so that
Since in each copy of there are at least two vertices which are not adjacent to vertices of other copies of
we need at least weight 2 to perfect Italian dominate each
If there are two copies of
with
then
Therefore, if possible assume that, there exists exactly one copy of
with
and all other copies have weight 2. Then either
or
For definiteness, let
Since both
and
are perfect Italian dominated by the vertices of
one of the following cases arises.
Case 1:
Since for
Since f is a perfect Italian dominating function
so that
for
To perfect Italian dominate
we must have
This implies, there exists at least two vertices
such that
for
and hence
which implies
for
which is a contradiction.
Case 2:
Then for the vertices either two vertices have weight 1 or one vertex has weight 2.
Subcase (a): for exactly two
and
for all other
For definiteness, let Since
for
To perfect Italian dominate
for
we must have
Since
To perfect Italian dominate
we must have
for
This implies,
which is a contradiction.
Subcase (b): for exactly one j and
for all other
For definiteness, let and
for
To perfect Italian dominate
we must have
Since
we must have
To perfect Italian dominate
we must have
This implies that
which is a contradiction.
Therefore, Hence,
□
Theorem 2.12.
The double Roman domination number of generalized Sierpiński graph is
Proof.
Let be the vertex set of
where
and
are the partite sets of the vertex set. Define a function f as follows.
Clearly, f is a DRDF and
To prove the reverse inequality, note that in each copy of in
there are at least two vertices which are not adjacent to other copies of
Hence, for any γdR-function f of
for all
so that
Therefore, in order to prove
we need only to prove that there does not exist any DRDF with weight 15, 16 or 17.
Claim 1: There does not exist a DRDF f with
Proof of Claim 1:
If there exists a DRDF f with then
for exactly one
For definiteness, let
Now to double Roman dominate
and
and
must be three. Since,
and
should be double Roman dominated by
and
respectively which makes
which is a contradiction.
Claim 2: There does not exist a DRDF f with
Proof of Claim 2:
If there exists a DRDF f with then
for exactly one i0 with
and
for every
Then at least one among
and
must be 3. For definiteness, let
Since
for every
we get the same contradiction as in the proof of claim 1.
Claim 3: There does not exist a DRDF f with
Proof of Claim 3:
If there exists a DRDF f with then the following two cases arise.
for exactly one i0 with
and
for every
for exactly two
say i0, j0 with
and
for every
In case (i) at least one among and
must be 3. For definiteness,
Then as in the proof of claim 1 we may take
If
then we get the same contradiction as in the proof of claim 1. Hence one among
and
must be 5. For definiteness let
Since
to double Roman dominate
But
is not get double Roman dominated and hence
which is a contradiction. Hence, we conclude that
□
Now we obtain the Italian domination number, perfect Italian domination number and double Roman domination number of Sierpiński graph of bistar when t = 2.
Theorem 2.13.
The Italian domination number of the generalized Sierpiński graph is
Proof.
Let be the vertex set of
Let
Define a function f on
as follows.
Clearly, f is an IDF and
so that
In each for
there are m + n leaves. To Italian dominate these copies we need at least weight 4. For that, it is optimum to assign weight 2 to the vertices
and
In
and
there are only n and m leaves, respectively. To Italian dominate these vertices we need at least weight 2. Therefore,
Hence,
□
Corollary 2.14.
The perfect Italian domination number of the generalized Sierpiński graph is
Proof.
In the proof of the above theorem we have defined an Italian dominating function with the property that every vertex with weight 0 is adjacent to exactly one vertex with weight 2. Therefore, We know that
Hence,
□
Theorem 2.15.
The double Roman domination number of the generalized Sierpiński graph is
Proof.
The proof is similar to that of Theorem 2.13 with the difference that the weight 2 is replaced by 3. □
References
- Ahangar, H. A., Chellali, M, Sheikholeslami, S. M. (2017). On the double Roman domination in graphs. Discrete Appl. Math. 232: 1–7.
- Alizadeh, F., Maimani, H. R., Majd, L. P, Parsa, M. R. (2022). Roman {2}-domination in graphs and graph products. Iran. J. Math. Sci. Inform. In Press.
- Amjadi, J., Nazari-Moghaddam, V., Sheikholeslami, S. M, Volkmann, L. (2018). An upper bound on the double Roman domination number. J. Comb. Optim. 36(6): 1–9.
- Anu, V, Aparna, L. S. (2018). Double Roman domination number. Discrete Appl. Math. 244: 198–204.
- Anu, V, Aparna, L. S. (2021). Impact of some graph operators on double Roman domination number. Int. J. Comb. Graph Theory Appl. 6(1): 97–105.
- Anu, V, Aparna, L. S. (2020). The double Roman domination number of generalized Sierpiński graphs. Discrete Math. Algorithms Appl. 12(4): Article 2050047.
- Aparna, L. S, Amala, B. (2022). Variations of Roman domination in Kneser graphs. Manuscript.
- Balakrishnan, R, Ranganathan, K. (1999). A Text Book of Graph Theory. New York: Springer.
- Beeler, R. A., Haynes, T. W, Hedetniemi, S. T. (2016). Double Roman domination. Discrete Appl. Math. 211(1): 23–29.
- Chellali, M., Haynes, T. W., Hedetniemi, S. T, McRae, A. A. (2016). Roman {2}-domination. Discrete Appl. Math. 204: 22–28.
- Chellai, M., Rad, N. J., Sheikholeslami, S. M, Volkmann, L. (2020). Roman domination in graphs. In: Haynes, T.W., Hedetniemi, S.T., Henning, M. A., eds. Topics in Domination in Graphs. Berlin/Heidelberg: Springer, pp. 365–409.
- Chellali, M., Jafari Rad, N., Sheikholeslami, S. M, Volkmann, L. (2020). Varieties of Roman Domination II. AKCE Int. J. Graphs Comb. 17(3): 966–984.
- Chellai, M., Rad, N. J., Sheikholeslami, S. M, Volkmann, L. (2021). Varieties of Roman Domination, Structures of Domination in Graphs. In: Haynes, T.W., Hedetniemi, S.T., Henning, M. A., eds. Topics in Domination in Graphs. Berlin/Heidelberg: Springer, pp. 273–307.
- Cockayne, E. J., Dreyer, P. A., Jr, Hedetniemi, S. M, Hedetniemi, S. T. (2004). Roman domination in graphs. Discrete Math. 278: 1–3.
- Deepalakshmi, J., Marimuthu, G., Somasundaram, A, Arumugam, S. (In press). Domination parameters of a splitting graph of a graph. Commun. Comb. Optim.
- Desormeaux, W. J., Haynes, T. W, Henning, M. A. (2018). Domination parameters of a graph and its complement. Discuss. Math. Graph Theory 38(1): 203–215.
- Gao, H., Xi, C., Li, K., Zhang, Q, Yang, Y. (2019). The Italian domination number of generalized Petersen graphs P(n,3). Mathematics 7(8): 714. Article 714.
- Gao, H., Xu, T, Yang, Y. (2019). Bagging approach for Italian domination in Cn□Pm. IEEE Access.
- Gravier, S., Kovše, M, Parreau, A. (2011). Generalized Sierpinski Graphs 1. https://www.semanticscholar.org/paper/Generalized-Sierpinski-graphs-1-Gravier-Kovse/3c21ce24174d1cdf788e2988702c1e81dc686436.
- Hajibaba, M, Rad, N. J. (2019). On domination, 2-domination and Italian domination numbers. Util. Math. 111: 271–280.
- Hao, G., Chen, X, Volkmann, L. (2019). Double Roman domination in digraphs. Bull. Malays. Math. Sci. Soc. 42(5): 1907–1920.
- Haynes, T. W., Henning, M. A, Volkman, L. (2020). Graphs with large Italian domination number. Bull. Malays. Math. Sci. Soc. 43(6): 4273–4287.
- Haynes, T. W, Henning, M. A. (2019). Perfect Italian domination in trees. Discrete Appl. Math. 260: 164–177.
- Henning, M. A, Klostermeyer, W. F. (2017). Italian domination in trees. Discrete Appl. Math. 217: 557–564.
- Hinz, A. M., Klavžar, S, Zemljicˇ, S. S. (2017). A survey and classification of Sierpiński-type graphs. Discrete Appl. Math. 217: 565–600.
- Jismy, V, Aparna, L. S. (2022). Impact of vertex addition on Italian domination number. Indian J. Discrete Math. 8(1): 11–20.
- Jismy, V., Anu, V, Aparna, L. S. (2021). Italian domination and perfect Italian domination on Sierpiński graphs. J. Discrete Math. Sci. Cryptogr. 24(7): 1885–1894.
- Jismy, V, Aparna, L. S. (2021). Italian domination on Mycielskian and Sierpiński graphs. Discrete Math. Algorithms Appl. 13(4): Article 2150037.
- Jismy, V, Aparna, L. S. (2022). Perfect Italian domination number of graphs. Palest. J. Math. 11(1): 260–270.
- Klavžar, S, Milutinović, U. (1997). Graphs S(n,k) and a variant of the tower of Hanoi problem. Czechoslov. Math. J. 47(1): 95–104.
- Klavžar, S., Milutinović, U, Petr, C. (2002). 1-Perfect codes in Sierpiński graphs. Bull. Austral. Math. Soc. 66(3): 369–384.
- Lauri, J, Mitillos, C. (2020). Perfect Italian domination on planar and regular graphs. Discrete Appl. Math. 285: 676–687.
- Liu, C. A. (2020). Domination in Sierpiński Graphs S(Kn,t). arXiv:2008.09807v1.
- Mojdeh, D. A., Masoumi, I, Volkman, L. (2022). Restrained double Roman domination of a graph. RAIRO-Oper. Res. 56(4): 2293–2304.
- Poureidi, A, Rad, N. J. (2020). On the algorithmic complexity of Roman {2}-domination. Iran. J. Sci. Technol. Trans. Sci. 44(3): 791–799.
- Poklukar, D. R, Zerovnik, J. (2022). On the double Roman domination in generalized Petersen graphs P(5k,k). Mathematics 10(1): Article 119.
- Ramezani, F., Rodríguez-Bazan, E. D, Rodríguez-Velázquez, J. A. (2017). On the Roman domination number of generalized Sierpiński graphs. Filomat 31(20): 6515–6528.
- Yang, H, Zhou, X. (2020). Some properties of double Roman domination. Discrete Dyn. Nat. Soc. 2020: 1–5. Article 6481092.