Open independent dominating set (OIND set) in the lexicographic product of graphs

• Lauane M. O. de Moraes UFG
• Erika M. M. Coelho UFG

DOI: https://doi.org/10.5753/etc.2024.2592

Abstract

For a graph G = (V (G), E(G)), a set S ⊆ V (G) is an open-independent dominating set, or OIND set, if for every v ∈ S, we have |N(v)∩S| ≤ 1, and for every v ∈ V (G), we have |N[v]∩S| ≥ 1. The minimum cardinality of the OIND set of G is denoted by γ_oind(G). We present some results for γ_oind(G) in simple classes of graphs and, given the lexicographic product of two graphs G and H , denoted by G ◦ H, we show bounds for γ_oind(G ◦ H).

References

Cockayne, E. J. and Hedetniemi, S. T. (1974). Independence graphs. In Graph Theory and Computing, Utilitas Math, pages 471–491. Conference on Combinatorics.

Cockayne, E. J. and Hedetniemi, S. T. (1977). Towards a theory of domination in graphs. In Networks 7, pages 247–261.

Gözüpek, D., Hujdurović, A., and Milanič, M. (2017). In Characterizations of minimal dominating sets and the well-dominated property in lexicographic product graphs, pages 1–17. Discrete Mathematics and Theoretical Computer Science.

Maheswari, S. U. and Parvathi, M. S. (2017). In Independent Dominating Sets of Lexicographic Product Graphs of Cayley Graphs with Arithmetic Graphs, pages 160–166. International Journal of Advanced in Management, Technology and Engineering Sciences.

Melo, L. F. and Coelho, E. M. M. (2019). Conjuntos dominantes independentes abertos no produto Lexicográfico de alguns grafos. Anais do XVI Congresso de Ensino Pesquisa e Extensão da UFG.

Seo, S. J. and Slater, P. J. (2017). In Open-independent, open-locating-dominating sets, pages 179–193. Elec. Journal of Graph Theory and Applications.

Sitthiwirattham, T. (2013). In Domination on Lexicographical Product of Complete Graph, pages 745–750. International Journal of Pure and Applied Mathematics.

Zhang, X., Liu, J., and Meng, J. (2011). In Domination in lexicographic product graphs, pages 251–256. Ars Combinatoria.