Article in press
Authors:
Title:
Independent [$k$]-Roman domination on graphs
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2024-06-28 , Revised: 2025-02-04 , Accepted: 2025-02-11 , Available online: 2025-02-22 , https://doi.org/10.7151/dmgt.2580
Abstract:
Given a function $f\colon V(G) \to \mathbb{Z}_{\geq 0}$ on a graph $G$, $AN(v)$
denotes the set of neighbors of $v \in V(G)$ that have positive labels under
$f$. In 2021, Abdollahzadeh Ahangar et al. introduced the notion of
$[k]$-Roman dominating function ([$k$]-RDF) of a graph $G$, which is a function $f\colon V(G) \to
\{0,1,\ldots,k+1\}$ such that $\sum_{u \in N[v]}f(u) \geq k + |AN(v)|$ for all
$v \in V(G)$ with $f(v)<k$. The weight of $f$ is $\sum_{v \in V(G)}f(v)$. The
$[k]$-Roman domination number, denoted by $\gamma_{[kR]}(G)$, is the minimum
weight of a $[k]$-RDF of $G$. The notion of [$k$]-RDF for $k=1$ has been
extensively investigated in the scientific literature since 2004, when
introduced by Cockayne et al. as Roman domination.
An independent [$k$]-Roman dominating function ([$k$]-IRDF) $f\colon V(G)
\to \{0,1,\ldots,k+1\}$ of a graph $G$ is a [$k$]-RDF of $G$ such that the
set of vertices with positive labels is an independent set. The independent
[$k$]-Roman domination number of $G$ is the minimum weight of a [$k$]-IRDF of
$G$ and is denoted by $i_{[kR]}(G)$. In this paper, we propose the study of
independent [$k$]-Roman domination on graphs for arbitrary $k \geq 1$. We prove
that, for all $k\geq 3$, the decision problems associated with $i_{[kR]}(G)$
and $\gamma_{[kR]}(G)$ are $\mathcal{NP}$-complete for planar bipartite graphs with
maximum degree 3. We also present lower and upper bounds for $i_{[kR]}(G)$.
Moreover, we present lower and upper bounds for the parameter $i_{[kR]}(G)$ for
a family of 3-regular graphs called generalized Blanuša snarks.
Keywords:
Roman domination, dominating set, independent set
References:
- H. Abdollahzadeh Ahangar, M.P. Álvarez, M. Chellali, S.M. Sheikholeslami and J.C. Valenzuela-Tripodoro, Triple Roman domination in graphs, Appl. Math. Comput. 391 (2021) 125444.
https://doi.org/10.1016/j.amc.2020.125444 - M. Adabi, E. Ebrahimi Targhi, N. Jafari Rad and M. {Saied} Moradi, Properties of independent Roman domination in graphs, Australas. J. Combin. 52 (2012) 11–18.
- J. Amjadi and N. Khalili, Quadruple Roman domination in graphs, Discrete Math. Algorithms Appl. 14(3) (2022) 2150130.
https://doi.org/10.1142/S1793830921501305 - R.A. Beeler, T.W. Haynes and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016) 23–29.
https://doi.org/10.1016/j.dam.2016.03.017 - D. Blanuša, Problem cetiriju boja, Glasnik Mat. Fiz. Astr. Ser. II 1 (1946) 31–42, in Croatian.
- M. Chellali, N. Jafari Rad, S. Sheikholeslami and L. Volkmann, A survey on Roman domination parameters in directed graphs, J. Combin. Math. Combin. Comput. 115 (2020) 141–171.
- M. Chellali, N. Jafari Rad, S.M. Sheikholeslami and L. Volkmann, Varieties of Roman domination II, AKCE Int. J. Graphs Comb. 17 (2020) 966–984.
https://doi.org/10.1016/j.akcej.2019.12.001 - M. Chellali, N. Jafari Rad, S.M. Sheikholeslami and L. Volkmann, Roman domination in graphs, in: Topics in Domination in Graphs, T.W. Haynes, S.T. Hedetniemi and M.A. Henning (Ed(s)), Dev. Math. 64, (Springer, Cham, 2020) 365–409.
https://doi.org/10.1007/978-3-030-51117-3_11 - M. Chellali, N. Jafari Rad, S.M. Sheikholeslami and L. Volkmann, Varieties of Roman domination, in: Structures of Domination in Graphs, T.W. Haynes, S.T. Hedetniemi and M.A. Henning (Ed(s)), Dev. Math. 66, (Springer, Cham, 2012) 273–307.
https://doi.org/10.1007/978-3-030-58892-2_10 - M. Chellali, N. Jafari Rad, S.M. Sheikholeslami and L. Volkmann, The Roman domatic problem in graphs and digraphs: a survey, Discuss. Math. Graph Theory 42 (2022) 861–891.
https://doi.org/10.7151/dmgt.2313 - E.J. Cockayne, P.A. Dreyer Jr, S.M. Hedetniemi and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004) 11–22.
https://doi.org/10.1016/j.disc.2003.06.004 - T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Domination in Graphs: Core Concepts, Springer Monogr. Math. (Springer, Cham, 2023).
https://doi.org/10.1007/978-3-031-09496-5 - M.C.N. Khalili, J. Amjadi, M. Chellali and S.M. Sheikholeslami, On $[k]$-Roman domination in graphs, AKCE Int. J. Graphs Comb. 20 (2023) 291–299.
https://doi.org/10.1080/09728600.2023.2241531 - A.G. Luiz, Roman domination and independent Roman domination on graphs with maximum degree three, Discrete Appl. Math. 348 (2024) 260–278.
https://doi.org/10.1016/j.dam.2024.02.006 - H. Maimani, M. Momeni, S.N. Moghaddam, F.R. Mahid amd S.M. Sheikholeslami, Independent double Roman domination in graphs, Bull. Iranian Math. Soc. 46 (2020) 543–555.
https://doi.org/10.1007/s41980-019-00274-8 - B. Mohar, Face covers and the genus problem for apex graphs, J. Combin. Theory Ser. B 82 (2001) 102–117.
https://doi.org/10.1006/jctb.2000.2026 - A.A. Pereira, Dominating Sets in Cubic Graphs, Master Thesis (University of Campinas, Institute of Computing, Campinas, Sao Paulo, Brazil, 2020), , in Portuguese..
- J. Petersen, Sur le théoreme de Tait, Interméd. Math. 5 (1898) 225–227.
- C.S. ReVelle and K.E. Rosing, Defendens imperium Romanum: a classical problem in military strategy, Amer. Math. Monthly 107 (2000) 585–594.
https://doi.org/10.1080/00029890.2000.12005243 - Z. Shao, P. Wu, H. Jiang, Z. Li, J. Žerovnik and X. Zhang, Discharging approach for double Roman domination in graphs, IEEE Access 6 (2018) 63345–63351.
https://doi.org/10.1109/ACCESS.2018.2876460 - I. Stewart, Defend the Roman empire!, Sci. Am. 281 (1999) 136–139.
https://doi.org/10.1038/scientificamerican1299-136 - P.G. Tait, On the colouring of maps, Proc. Roy. Soc. Edinburgh Sect. A 10 (1880) 501–503.
https://doi.org/10.1017/S0370164600044229 - J.C. Valenzuela-Tripodoro, M.A. Mateos-Camacho, M. Cera Lopez, M.P. Alvarez-Ruiz, Further results on the $[k]$-Roman domination in graphs, Bull. Iranian Math. Soc. 50 (2024) 27.
https://doi.org/10.1007/s41980-024-00872-1 - J.J. Watkins, On the construction of snarks, Ars Combin. 16 (1983) 111–123.
Close