Alianzas defensivas fuertes en gráficas clásicas bajo el operador S(G) y R(G)

Authors

  • Raúl Juárez Morales
  • Concepción Rojas Casarrubias
  • Luis Alberto Lucrecio González
  • José Ángel Juárez Morales
  • Rubén García Medina

DOI:

https://doi.org/10.46932/sfjdv4n10-010

Keywords:

gráficas, alianzas defensivas, operadores de gráficas

Abstract

Sea  una gráfica finita, simple y conexa, con conjunto de vértices  y conjunto de arista , donde  es el orden de ,  es el tamaño de . La gráfica S(G) se obtiene insertando un vértice adicional en cada arista de  o equivalentemente reemplazando cada una de sus aristas por un camino de longitud dos. La gráfica  es la que se obtiene a partir de , agregando un nuevo vértice por cada arista de  y uniendo cada vértice nuevo a los extremos de la arista correspondiente a él. En este trabajo se obtienen fórmulas cerradas para el número de alianza defensiva fuerte para las gráficas clásicas (Completa, Bipartita Completa, Doble Estrella, k-Regular y Rueda) bajo los operadores  y .

References

Basilio, L. A., Castro Simon, J., Leaños, J., y Rosario Cayetano, O. (2020). The differential on graph operator Q (G). Symmetry, 12(5), 751. https://doi.org/10.3390/sym12050751

Bermudo, S. (2023). Total domination on tree operators. Mediterranean Journal of Mathematics, 20(1), 42.

Bindusree, A. R., Cangul, I. N., Lokesha, V., y Cevik, A. S. (2016). Zagreb polynomials of three graph operators. Filomat, 30(7), 1979-1986.

Bondy J.A. y Murty U.S.R. (2008). Graph theory. San Francisco, USA: SPRINGER, 651p.

Brigham, R. C., Dutton, R. D., Haynes, T. W., y Hedetniemi, S. T. (2009). Powerful alliances in graphs. Discrete Mathematics, 309(8), 2140-2147.

Castro, J., Basilio, L. A., Reyna, G., & Rosario, O. (2023). The differential on operator ${{mathcal {S}}({Gamma})} $. Mathematical Biosciences and Engineering, 20(7), 11568-11584.

Dickson, P. H., y Weaver, K. M. (2005). R&D alliance formation: the relationship between national R&D intensity and SME size. Proceedings of ICSB 50th world conference DC, 123-154.

Dourado, M. C., Faria, L., Pizana, M. A., Rautenbach, D., y Szwarcfiter, J. L. (2014). On defensive alliances and strong global offensive alliances. Discrete Applied Mathematics, 163, 136-141.

Fomin, F.V., Grandoni, F. y Kratsch, D. (2009). A measure and conquer approach for the analysis of exact algorithms. Journal of the ACM , 56, 1–32.

Gaspers, S., Kratsch, D., Liedloff, M. y Todinca, I. (2009). Exponential time algorithms for the minimum dominating set problem on some graph classes. ACM Transactions on Algorithms, 6, 1–21.

Harary, F., y Norman, R. Z. (1960). Some properties of line digraphs. Rendiconti del circolo matematico di palermo, 9, 161-168.

Haynes, T. W., Hedetniemi, S. T., y Henning, M. A. (2003). Global defensive alliances in graphs. The electronic journal of combinatorics, R47-R47.

Haynes, T., Knisley, D., Seier, E., y Zou, Y. (2006). A quantitative analysis of secondary RNA structure using domination based parameters on trees. BMC bioinformatics, 7, 1-11.

Kristiansen, P., Hedetniemi, S.M. y Hedetniemi, S.T. (2004). Alliances in graphs, J. Combin. Math. Combin. Comput. 48 157–177.

Méndez-Bermúdez, J. A., Reyes, R., Rodríguez, J. M., y Sigarreta, J. M. (2018). Hyperbolicity on graph operators. Symmetry, 10(9), 360.

Ouatiki, S., y Bouzefrane, M. (2021). A lower bound on the global powerful alliance number in trees. RAIRO-Operations Research, 55(2), 495-503.

Rad, N. J. (2018). A note on the global offensive alliances in graphs. Discrete Applied Mathematics, 250, 373-376.

Ranjini, P. S., y Lokesha, V. (2010). Smarandache-Zagreb index on three graph operators. International Journal of Mathematical Combinatorics, 3, 1.

Rodríguez-Velázquez, J. A., y Sigarreta, J. M. (2006). Global offensive alliances in graphs. Electronic Notes in Discrete Mathematics, 25, 157-164.

Seba, H., Lagraa, S., y Kheddouci, H. (2012). Alliance-based clustering scheme for group key management in mobile ad hoc networks. The Journal of Supercomputing, 61, 481-501.

Sigarreta, J. M. (2021). Total domination on the T (G) operator. Private communication.

Sigarreta, J. M. (2021). Total domination on some graph operators. Mathematics, 9(3), 241.

Sigarreta, J. M., y Rodríguez, J. A. (2006). On defensive alliances and line graphs. Applied Mathematics Letters, 19(12), 1345-1350.

Srimani, P. K., y Xu, Z. (2007, March). Distributed protocols for defensive and offensive alliances in network graphs using self-stabilization. In 2007 International Conference on Computing: Theory and Applications (ICCTA'07) (pp. 27-31). IEEE.

Van Rooij, J.M. y Bodlaender, H.L. (2011). Exact algorithms for dominating set. Discrete Applied Mathematics, 159, 2147–2164.

Downloads

Published

2023-12-15

How to Cite

Morales, R. J., Casarrubias, C. R., González, L. A. L., Morales, J. Ángel J., & Medina, R. G. (2023). Alianzas defensivas fuertes en gráficas clásicas bajo el operador S(G) y R(G). South Florida Journal of Development, 4(10), 3859–3872. https://doi.org/10.46932/sfjdv4n10-010