1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Total and Paired Domination Stability in Prisms

Published Online: 05 Aug 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 07 Dec 2020
Accepted: 01 Jul 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
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 γt(G) and the paired domination number γ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 st γt (G) (respectively, stγ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

MSC 2010

[1] M. Amraee, N. Jafari Rad and M. Maghasedi, Roman domination stability in graphs, Math. Rep. (Bucur.) 21(71) (2019) 193–204.Search in Google Scholar

[2] S. Arumugam and R. Kala, Domination parameters of hypercubes, J. Indian Math. Soc. (N.S.) 65 (1998) 31–38.Search in Google Scholar

[3] 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/628810.37236/6288Search in Google Scholar

[4] A. Aytaç and B. Atay Atakul, Exponential domination critical and stability in some graphs, Internat. J. Found. Comput. Sci. 30 (2019) 781–791. https://doi.org/10.1142/S012905411950021710.1142/S0129054119500217Search in Google Scholar

[5] 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-710.1016/0012-365X(83)90085-7Search in Google Scholar

[6] 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-010.1007/s10878-017-0150-0Search in Google Scholar

[7] A. Gorzkowska, M.A. Henning, M. Pilśniak and E. Tumidajewicz, Paired domination stability in graphs, (2020), manuscript.10.26493/1855-3974.2522.eb3Search in Google Scholar

[8] 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-K10.1016/0893-9659(93)90027-KSearch in Google Scholar

[9] 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-810.1007/s10878-007-9135-8Search in Google Scholar

[10] 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-FSearch in Google Scholar

[11] 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.02210.1016/j.dam.2017.07.022Search in Google Scholar

[12] 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-810.1007/s00373-004-0586-8Search in Google Scholar

[13] M.A. Henning and A. Yeo, Total Domination in Graphs (Springer Monographs in Mathematics, 2013). https://doi.org/10.1007/978-1-4614-6525-610.1007/978-1-4614-6525-6Search in Google Scholar

[14] 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-010.1007/s10878-019-00414-0Search in Google Scholar

[15] 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.00710.1016/j.ejc.2010.11.007Search in Google Scholar

[16] 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.152610.7151/dmgt.1526Search in Google Scholar

[17] 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.94526810.1109/18.945268Search in Google Scholar

[18] 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.02610.1016/j.disc.2015.12.026Search in Google Scholar

[19] 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.263210.1109/18.2632Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo