Dominating Sets and Independent Dominating Sets in Generalized Petersen Graphs
Abstract
A dominating set of a graph G is a set S of vertices such that every vertex in G is either in S or is adjacent to a vertex in S. An independent dominating set of G is both dominating and independent in G. In this work, we study dominating and independent dominating sets of Generalized Petersen graphs.
Keywords:
Dominating Sets, Independent Dominating Sets, Domination Number, Independent Domination Number, Generalized Petersen graphs
References
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.
Published
2020-06-30
How to Cite
PEREIRA, A. A.; CAMPOS, C. N..
Dominating Sets and Independent Dominating Sets in Generalized Petersen Graphs. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (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.
