Conjunto dominante independente aberto (OIND set) em produto lexicográfico de grafos
Resumo
Para um grafo G = (V (G), E(G)), um conjunto S ⊆ V (G) é um conjunto dominante independente aberto, ou conjunto OIND, se para todo v ∈ S, temos que |N(v) ∩ S| ≤ 1, e para todo v ∈ V (G), temos que |N [v] ∩ S| ≥ 1. A cardinalidade mínima do conjunto OIND de G é denotada por γoind(G). Neste trabalho mostramos alguns resultados para γoind(G) em classes simples de grafos e, dado o produto lexicográfico de dois grafos G e H, denotado por G ◦ H, nós mostramos limites para γoind(G ◦ H).
Referências
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.
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.
Publicado
21/07/2024
Como Citar
MORAES, Lauane M. O. de; COELHO, Erika M. M..
Conjunto dominante independente aberto (OIND set) em produto lexicográfico de grafos. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 9. , 2024, Brasília/DF.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 76-80.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2024.2592.
