New constructions for the n-queens problem

DOI10.1007/S00025-020-1166-9MaRDI QIDQ2302227zbMATH OpenOpenAlexFDO

Authors Martin Bača, Andrea Semaničová-Feňovčíková, S. C. López, F. A. Muntaner-Batle

Publication date 25 February 2020

Published in Results in Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.09942

zbMATH Keywords

(modular) \(n\)-queens problem(modular) queen labeling\( \otimes_h\)-product

Mathematics Subject Classification ID

Graph operations (line graphs, products, etc.) (05C76) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: Let $D$ be a digraph, possibly with loops. A queen labeling of $D$ is a bijective function $l:V(G)longrightarrow1,2,ldots,|V(G)|$ such that, for every pair of arcs in $E(D)$, namely $(u,v)$ and $(u^{\prime },v^{\prime })$ we have (i) $l(u)+l(v)eql(u^{\prime })+l(v^{\prime })$ and (ii) $l(v)-l(u)eql(v^{\prime })-l(u^{\prime })$. Similarly, if the two conditions are satisfied modulo $n=|V(G)|$, we define a modular queen labeling. There is a bijection between (modular) queen labelings of $1$-regular digraphs and the solutions of the (modular) $n$-queens problem. The $otime{s}_h$-product was introduced in 2008 as a generalization of the Kronecker product and since then, many relations among labelings have been established using the $otime{s}_h$-product and some particular families of graphs. In this paper, we study some families of $1$-regular digraphs that admit (modular) queen labelings and present a new construction concerning to the (modular) $n$-queens problem in terms of the $otime{s}_h$-product, which in some sense complements a previous result due to P'olya.

Recommendations

• Queen labelings
• Polynomial modular n-queens solutions
• Queens graphs
• scientific article; zbMATH DE number 4127220
• A contribution to queens graphs: a substitution method

Cites work

• A dynamic survey of graph labeling
• A problem on edge-magic labelings of cycles
• A survey of known results and research areas for \(n\)-queens
• Bi-magic and other generalizations of super edge-magic labelings
• Graceful, harmonious and magic type labelings. Relations and techniques
• Handbook of product graphs
• scientific article; zbMATH DE number 1614340 (Why is no real title available?)
• scientific article; zbMATH DE number 5360700 (Why is no real title available?)
• scientific article; zbMATH DE number 4089545 (Why is no real title available?)
• scientific article; zbMATH DE number 1269934 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• Labeling constructions using digraph products
• Labeling generating matrices
• Magic Valuations of Finite Graphs
• Perfect (super) edge-magic crowns
• Queen labelings
• Strongly indexable graphs
• The jumping knight and other (super) edge-magic constructions
• The n-Queens Problem
• The place of super edge-magic labelings among other classes of labelings
• The power of digraph products applied to labelings

Cited in

(3)

• Linear congruence equations for the solutions of the N-queens problem
• scientific article; zbMATH DE number 5064060 (Why is no real title available?)
• Queen labelings

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: New constructions for the \(n\)-queens problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2302227)