Conjuntos Dominantes e Dominantes Independentes em Grafos de Petersen Generalizados
Resumo
Um conjunto S ⊆ V (G) é um conjunto dominante se todo vértice de G é um elemento de S ou é adjacente a um elemento de S. Um conjunto dominante independente de G é, ao mesmo tempo, um conjunto dominante e um conjunto independente em G. Neste trabalho, estudamos conjuntos dominantes e conjuntos dominantes independentes dos Grafos de Petersen Generalizados.
Palavras-chave:
Conjuntos Dominantes, Conjuntos Dominantes Independentes, Número de Dominação, Número de Dominação Independente, Grafos de Petersen Generalizados
Referências
Alvarado, J. D., Dantas, S., e Rautenbach, D. (2015). Complexity of comparing the domination number to the independent domination, connected domination, and paired domination numbers. Matemática Contemporânea, 44(1):1–8.
Blank, M. (1973). An estimate of the external stability number of a graph without suspended vertices. Prikl. Math. i Programmirovanie, 10:3–11.
Ebrahimi, B. J., Jahanbakht, N., e Mahmoodian, E. S. (2009). Vertex domination of generalized petersen graphs. Discrete mathematics, 309(13):4355–4361.
Garey, M. R. e Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, US.
Kostochka, A. V. e Stodolsky, B. Y. (2005). On domination in connected cubic graphs. Discrete mathematics, 304(1–3):45–50.
Liu, C. H., Poon, S. H., e Lin, J. Y. (2015). Independent dominating set problem revisited. Theoretical Computer Science, 562:1–22.
McCuaig, W. e Shepherd, B. (1989). Domination in graphs with minimum degree two. Journal of Graph Theory, 13(6):749–762.
Ore, O. (1962). Theory of Graphs. American Mathematical Society, Providence, US.
Reed, B. (1996). Paths, stars and the number three. Combinatorics, Probability and Computing, 5(3):277–295.
Žerovnik, J. e Oplerova, J. (1993). A counterexample to conjecture of Barefoot, Harary, and Jones. Graphs and Combinatorics, 9(2–4):205–207.
Watkins, M. E. (1969). A theorem on Tait colorings with an application to the generalized Petersen graphs. Journal of Combinatorial Theory, 6(2):152–164.
Blank, M. (1973). An estimate of the external stability number of a graph without suspended vertices. Prikl. Math. i Programmirovanie, 10:3–11.
Ebrahimi, B. J., Jahanbakht, N., e Mahmoodian, E. S. (2009). Vertex domination of generalized petersen graphs. Discrete mathematics, 309(13):4355–4361.
Garey, M. R. e Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, US.
Kostochka, A. V. e Stodolsky, B. Y. (2005). On domination in connected cubic graphs. Discrete mathematics, 304(1–3):45–50.
Liu, C. H., Poon, S. H., e Lin, J. Y. (2015). Independent dominating set problem revisited. Theoretical Computer Science, 562:1–22.
McCuaig, W. e Shepherd, B. (1989). Domination in graphs with minimum degree two. Journal of Graph Theory, 13(6):749–762.
Ore, O. (1962). Theory of Graphs. American Mathematical Society, Providence, US.
Reed, B. (1996). Paths, stars and the number three. Combinatorics, Probability and Computing, 5(3):277–295.
Žerovnik, J. e Oplerova, J. (1993). A counterexample to conjecture of Barefoot, Harary, and Jones. Graphs and Combinatorics, 9(2–4):205–207.
Watkins, M. E. (1969). A theorem on Tait colorings with an application to the generalized Petersen graphs. Journal of Combinatorial Theory, 6(2):152–164.
Publicado
30/06/2020
Como Citar
PEREIRA, A. A.; CAMPOS, C. N..
Conjuntos Dominantes e Dominantes Independentes em Grafos de Petersen Generalizados. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 5. , 2020, Cuiabá.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2020
.
p. 53-56.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2020.11088.
