Graph dominance by rook domains for Znp and Zn3 × Zm2 graphs

• Piza Volio, Eduardo ^[1]
  1. [1] Universidad de Costa Rica

     Universidad de Costa Rica

     Hospital, Costa Rica

     
• Localización: Revista de Matemática: Teoría y Aplicaciones, ISSN 2215-3373, ISSN-e 2215-3373, Vol. 11, Nº. 2, 2004, págs. 55-70
• Idioma: inglés
• DOI: 10.15517/rmta.v11i2.243
• Enlaces
  • Texto completo (pdf)
• Resumen
  • español

    En este art´?culo se describe el problema de la dominaci´on de los grafos del tipo Znpy mezclas del tipo Zn3×Zm2a trav´es de subconjuntos dominantes de v´ertices de tama˜nom´?nimo. Se introduce un algoritmo del tipo de recocido simulado para calcular cotassuperiores de la cardinalidad de estos subconjuntos dominantes minimales.Se demuestra la eficiencia del algoritmo al comparar los resultados obtenidos conlos ya conocidos correspondientes a algunas clases de grafos, entre ellos los llamadosgrafos del “football pool problem”. Se establecen cotas superiores en algunos de losgrafos del tipo Znp, con p 4. Los c´odigos de algunos subconjuntos dominantes seincluyen en un ap´endice.Palabras clave: Dominaci´on de grafos, recocido simulado, problema de las apuestas enf´utbol, combinatoria.

  • English

    Described within is the problem of finding near-minimum dominating subsets of agiven graph by rook domains. Specifically, we study the graphs of the kind ZnpandZn3×Zm2and introduce a simulated annealing algorithm to compute upper bounds ofthe size of minimum dominating subsets.We demonstrate the effectiveness of the algorithm by comparing the results with apreviously studied class of graphs, including the so-called “football pool” graphs andothers. We give some new upper bounds for graphs of the kind Znp, with p 4. Thecodes of some dominating subsets are given in an appendix.Keywords: Graph domination, simulated annealing, football pool problem, combinatorics.

• Referencias bibliográficas
  • Aarts, E.; Korst, J. (1990) Simulated Annealing and Boltzmann Machines. A Stochastic Approach to Combinatorial Optimization and Neural Computing...
  • Biggs, N. (1974) Algebraic Graph Theory. Cambridge University Press.
  • Blokhuis, A.; Lam, C.W.H. (1984) “More coverings by rook domains”, Journal of Combinatorial Theory, Series A 36: 240–244.
  • Cameron, P.J.; van Lint, J.H. (1991) Designs, Graphs, Codes and their Links. London Mathematical Society Student Texts, 22, Cambridge University...
  • Davies, R.; Royle, G.F. (1997) “Graph domination, tabu search and the football pool problem”, Discrete Applied Mathematics 74(3): 217–228.
  • Garey, M.; Johnson, D. (1979) Computers and Intractability: a Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco.
  • Hämäläinen, H.O.; Rankinen, S. (1991) “Upper bounds for football pool problem and mixed covering codes”, Journal of Combinatorial Theory,...
  • Knuth, D.E. (1981) Seminumerical Algorithms. Second edition, volume 2 of the book The Art of Computer Programming . Addison-Wesley, Reading,...
  • Koschnick, K.U. (1993) “A new upper bound for the football pool problem for nine matches”, Journal of Combinatorial Theory, Series A, 62:...
  • van Laarhoven, P.J.M. (1988) “Theoretical and computational aspects of simulated annealing”, Centrum voor Wiskunde in Informatica, Tract 57.
  • van Laarhoven, P.J.M.; Aarts, E.J.L.; van Lint, J.H.; Wille, L.T. (1989) “New upper bounds for the football pool problem for 6, 7 and 8 matches”,...
  • Österg̊ard, P.R.J.; Hämäläinen, H.O. (s.f.) “A new table of binary/ternary mixed covering codes”, Preprint.
  • Österg̊ard, P.R.J. (1994) “New upper bound for the football pool problem for 11 and 12 matches”, Journal of Combinatorial Theory, Series...
  • Österg̊ard, P.R.J. (1995) “A combinatorial proof for the football pool problem for six matches”, Journal of Combinatorial Theory, Series...
  • Piza, E.; Trejos, J.; Murillo, A. (1998) “Global stochastic optimization techniques applied to partitioning”, in A. Rizzi et al. (Eds.) Advances...
  • Wille, L.T. (1987) “The football pool problem for 6 matches: A new upper bound obtained by simulated annealing”, Journal of Combinatorial...