Article in volume
Authors:
Title:
Total and paired domination stability in prisms
PDFSource:
Discussiones Mathematicae Graph Theory 43(4) (2023) 1147-1169
Received: 2020-12-07 , Revised: 2021-07-01 , Accepted: 2021-07-01 , Available online: 2021-07-16 , https://doi.org/10.7151/dmgt.2421
Abstract:
A set $D$ of vertices in an isolate-free graph is a total dominating set if
every vertex is adjacent to a vertex in $D$. If the set $D$ has the additional
property that the subgraph induced by $D$ contains a perfect matching, then $D$
is a paired dominating set of $G$. The total domination number $\gamma_{t}(G)$ and the
paired domination number $\gamma_\textrm{pr}(G)$ of a graph $G$ are the minimum cardinalities
of a total dominating set and a paired dominating set of $G$, respectively. The
total domination stability (respectively, paired domination stability) of $G$,
denoted $\textrm{st}_{\gamma_t}(G)$ (respectively, $\textrm{st}_{\gamma_\textrm{pr}}(G)$), is the minimum size of a
non-isolating set of vertices in $G$ whose removal changes the total domination
number (respectively, paired domination number). In this paper, we study total
and paired domination stability in prisms.
Keywords:
total domination stability, paired domination stability, prism, hypercube
References:
- M. Amraee, N. Jafari Rad and M. Maghasedi, Roman domination stability in graphs, Math. Rep. (Bucur.) 21(71) (2019) 193–204.
- S. Arumugam and R. Kala, Domination parameters of hypercubes, J. Indian Math. Soc. (N.S.) 65 (1998) 31–38.
- J. Azarija, M.A. Henning and S. Klavžar, $($Total$)$ domination in prisms, Electron. J. Combin. 24(1) (2017) #P1.19.
https://doi.org/10.37236/6288 - A. Aytaç and B. Atay Atakul, Exponential domination critical and stability in some graphs, Internat. J. Found. Comput. Sci. 2019 (781–791).
https://doi.org/10.1142/S0129054119500217 - D. Bauer, F. Harary, J. Nieminen and C.L. Suffel, Domination alternation sets in graphs, Discrete Math. 47 (1983) 153–161.
https://doi.org/10.1016/0012-365X(83)90085-7 - W. Goddard and M.A. Henning, A note on domination and total domination in prisms, J. Comb. Optim. 35 (2018) 14–20.
https://doi.org/10.1007/s10878-017-0150-0 - A. Gorzkowska, M.A. Henning, M. Pilśniak and E. Tumidajewicz, Paired domination stability in graphs, (2020), manuscript.
- F. Harary and M. Livingston, Independent domination in hypercubes, Appl. Math. Lett. 6 (1993) 27–28.
https://doi.org/10.1016/0893-9659(93)90027-K - T.W. Haynes, M.A. Henning and L.C. van der Merwe, Domination and total domination in complementary prisms, J. Comb. Optim. 18 (2009) 23–37.
https://doi.org/10.1007/s10878-007-9135-8 - T.W. Haynes and P.J. Slater, Paired domination in graphs, Networks 32 (1998) 199–206.
https://doi.org/10.1002/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F - M.A. Henning and M. Krzywkowski, Total domination stability in graphs, Discrete Appl. Math. 236 (2018) 246–255.
https://doi.org/10.1016/j.dam.2017.07.022 - M.A. Henning and D.F. Rall, On the total domination number of Cartesian products of graphs, Graphs Combin. 21 (2005) 63–69.
https://doi.org/10.1007/s00373-004-0586-8 - M.A. Henning and A. Yeo, Total Domination in Graphs (Springer Monographs in Mathematics, 2013).
https://doi.org/10.1007/978-1-4614-6525-6 - Z. Li, Z. Shao and S.J. Xu, $2$-rainbow domination stability of graphs, J. Comb. Optim. 38 (2019) 836–845.
https://doi.org/10.1007/s10878-019-00414-0 - M. Mollard, On perfect codes in Cartesian product of graphs, European J. Combin. 32 (2011) 398–403.
https://doi.org/10.1016/j.ejc.2010.11.007 - C.M. Mynhardt and M. Schurch, Paired domination in prisms of graphs, Discuss. Math. Graph Theory 31 (2011) 5–23.
https://doi.org/10.7151/dmgt.1526 - P.R.J. Östergård and U. Blass, On the size of optimal binary codes of length $9$ and covering radius $1$, IEEE Trans. Inform. Theory 47 (2001) 2556–2557.
https://doi.org/10.1109/18.945268 - N. Jafari Rad, E. Sharifi and M. Krzywkowski, Domination stability in graphs, Discrete Math. 339 (2016) 1909–1914.
https://doi.org/10.1016/j.disc.2015.12.026 - G.J.M. van Wee, Improved sphere bounds on the covering radius of codes, IEEE Trans. Inform. Theory 34 (1988) 237–245.
https://doi.org/10.1109/18.2632
Close