On the maximum number of non-attacking rooks on a high-dimensional simplicial chessboard

DOI10.1007/S00373-022-02456-4MaRDI QIDQ2117514zbMATH OpenOpenAlexFDO

Authors A. Ahadi, Mohsen Mollahajiaghaei, A. Dehghan

Publication date 21 March 2022

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

automorphism groupcomputational complexitycyclic simplicial rook graphindependence numbersimplicial rook graph

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Combinatorial aspects of partitions of integers (05A17) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Analysis of algorithms and problem complexity (68Q25)

Abstract: The simplicial rook graph $mmathcalSR(m,n)$ is the graph whose vertices are vectors in $mathbb{N}^m$ such that for each vector the summation of its coordinates is $n$ and two vertices are adjacent if their corresponding vectors differ in exactly two coordinates. Martin and Wagner (Graphs Combin. (2015) 31:1589--1611) asked about the independence number of $mmathcalSR(m,n)$ that is the maximum number of non attacking rooks which can be placed on a $(m-1)$-dimensional simplicial chessboard of side length $n+1$. In this work, we solve this problem and show that $$. We also prove that for the domination number of rook graphs we have $gamma(mmathcalSR(m,n))=Theta(n^{m-2})$. Moreover we show that these graphs are Hamiltonian. The cyclic simplicial rook graph $mmathcalCSR(m,n)$ is the graph whose vertices are vectors in $mathbb{Z}_n^m$ such that for each vector the summation of its coordinates modulo $n$ is $0$ and two vertices are adjacent if their corresponding vectors differ in exactly two coordinates. In this work we determine several properties of these graphs such as independence number, chromatic number and automorphism group. Among other results, we also prove that computing the distance between two vertices of a given $mmathcalCSR(m,n)$ is $mathbfNP$-hard in terms of $n$ and $m$.

Recommendations

• Notes on simplicial rook graphs
• scientific article; zbMATH DE number 2077666
• scientific article; zbMATH DE number 1124599

Cites work

• scientific article; zbMATH DE number 3657869 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• scientific article; zbMATH DE number 3349875 (Why is no real title available?)
• Notes on simplicial rook graphs

Cited in

(2)

• Notes on simplicial rook graphs
• On the spectra of simplicial rook graphs

This page was built for publication: On the maximum number of non-attacking rooks on a high-dimensional simplicial chessboard

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