Power domination in generalized Mycielskian of spiders
DOI:
https://doi.org/10.7146/math.scand.a-147931Abstract
The power domination problem in the graph was introduced to model the monitoring problem in electric networks. It is to find a set of vertices with minimum cardinality, called a power dominating set (PDS), that monitors the whole set $ V $ after applying the rules, domination and propagation. In this paper, we discuss the power domination problem in generalized Mycielskian of spiders. We characterize spiders with $\gamma _P(\mu _m(T))= 1$. If $\gamma _P(\mu _m(T))\neq 1 $ and $ m $ is even then $ \gamma _P(\mu _m(T))=\frac {m}{2} +1$. We also show that if $ m $ is odd and $ \gamma _P(\mu _m(T))\neq 1 $, then $ \lceil \frac {m+1}{2}\rceil \leq \gamma _P(\mu _m(T))\leq \lceil \frac {m}{2}\rceil +1$.
References
Balakrishnan, R., and Francis Raj, S., Connectivity of the Mycielskian of a graph, Discrete Math. 308 (2008), no. 12, 2607–2610. https://doi.org/10.1016/j.disc.2007.05.004
Baldwin, T. L., Mili, L., Boisen, M. B., and Adapa, R., Power system observability with minimal phasor measurement placement, IEEE Trans. Power Syst. 8 (1993), no. 2, 707–715.
Barrera, R., and Ferrero, D., Power domination in cylinders, tori, and generalized Petersen graphs, Networks 58 (2011), no. 1, 43–49. https://doi.org/10.1002/net.20413
Dorbec, P., Mollard, M., Klavžar, S., and Špacapan, S., Power domination in product graphs, SIAM J. Discrete Math. 22 (2008), no. 2, 554–567. https://doi.org/10.1137/060661879
Dorfling, M., and Henning, M. A., A note on power domination in grid graphs, Discrete Appl. Math. 154 (2006), no. 6, 1023–1027. https://doi.org/10.1016/j.dam.2005.08.006
Ferrero, D., Varghese, S., and Vijayakumar, A., Power domination in honeycomb networks, J. Discrete Math. Sci. Cryptogr. 14 (2011), no. 6, 521–529. https://doi.org/10.1080/09720529.2011.10698353
Lin, W., Wu, J., Lam, P. C. B., and Gu, G., Several parameters of generalized Mycielskians, Discrete Appl. Math. 154 (2006), no. 8, 1173–1182. https://doi.org/10.1016/j.dam.2005.11.001
Haynes, T. W., Hedetniemi, S. M., Hedetniemi, S. T., and Henning, M. A., Domination in graphs applied to electric power networks, SIAM J. Discrete Math. 15 (2002), no. 4, 519–529. https://doi.org/10.1137/S0895480100375831
K, S., Varghese, S., and Varghese, S., Power domination in Mycielskians of $n$-spiders, AKCE Int. J. Graphs. Comb. (2023), to appear. https://doi.org/10.1080/09728600.2023.2296501
Mycielski, J., Sur le coloriage des graphs, Colloq. Math. 3 (1955), 161–162. https://doi.org/10.4064/cm-3-2-161-162
Savitha, K. S., Chithra, M. R., and Vijayakumar, A., Some diameter notions of the generalized Mycielskian of a graph, Theoretical computer science and discrete mathematics, 371–382, Lecture Notes in Comput. Sci., 10398, Springer, Cham, 2017. https://doi.org/10.1007/978-3-319-64419-6
Stephen, S., Rajan, B., Ryan, J., Grigorious, C., and William, A., Power domination in certain chemical structures, J. Discrete Algorithms 33 (2015), 10–18. https://doi.org/10.1016/j.jda.2014.12.003
Varghese, S., and Vijayakumar, A., Studies on some generalizations of line graph and the power domination problem in graphs, PhD thesis, (2011).
Varghese, S., Varghese, S., and Vijayakumar, A., Power domination in Mycielskian of spiders, AKCE Int. J. Graphs. Comb. 19 (2022), no. 2, 154–158. https://doi.org/10.1080/09728600.2022.2082900
Varghese, S., Vijayakumar, A., and Hinz, A. M., Power domination in Knödel graphs and Hanoi graphs, Discuss. Math. Graph Theory 38 (2018), no. 1, 63–74. https://doi.org/10.7151/dmgt.1993
Sreethu, K., Varghese, S., and Varghese, S., Power domination in Mycielskians of $n$-spiders, AKCE Int. J. Graphs. Comb. (2023), to appear. https://doi.org/10.1080/09728600.2023.2296501
West, D. B., Introduction to graph theory, ed. 2. Prentice Hall Upper Saddle River, (2001).
Xu, G., Kang, L., Shan, E., and Zhao, M., Power domination in block graphs, Theoret. Comput. Sci. 359 (2006), no. 1–3, 299–305. https://doi.org/10.1016/j.tcs.2006.04.011
