Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/2784

Queen Labelings
Bloom, Gary; Lampis, Michael; Muntaner Batle, Francesc Antoni; Rius Font, Miquel
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV; Universitat Politècnica de Catalunya. COMBGRAF - Combinatòria, Teoria de Grafs i Aplicacions
We introduce and investigate the concept of Queen labeling a digraph and its connection to the well-known n-queens problem. In the general case we obtain an upper bound on the size of a queen graph and show that it is tight. We also examine the existence of possible forbid-den subgraphs for this problem and show that only two such subgraphs exist. Then we focus on specific graph families: First we show that every star is a queen graph by giving an algorithm for which we prove cor-rectness. Then we show that the problem of queen labeling a matching is equivalent to a variation of the n-queens problem, which we call the rooks-and-queens problem and we use that fact to give a short proof that every matching is a queen graph. Finally, for unions of 3-cycles we give a general solution of the problem for graphs of n(n - 1) vertices.
Àrees temàtiques de la UPC::Matemàtiques i estadística
Graph labelings
Labeling
Grafs, Teoria de
Classificació AMS::05 Combinatorics::05C Graph theory
Artículo
         

Mostrar el registro completo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

López Masip, Susana Clara; Muntaner Batle, Francesc Antoni; Rius Font, Miquel
López Masip, Susana Clara; Muntaner Batle, Francesc Antoni; Rius Font, Miquel
Ahmad, Ali; López Masip, Susana Clara; Muntaner Batle, Francesc Antoni; Rius Font, Miquel
Muntaner Batle, Francesc Antoni; Rius Font, Miquel; Ichishima, Rikio; Figueroa Centeno, Ramon M.
Muntaner Batle, Francesc Antoni; Rius Font, Miquel