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

DOI10.1007/S00373-022-02456-4zbMATH Open1485.05124arXiv2102.00535OpenAlexW3128084495MaRDI QIDQ2117514FDOQ2117514

A. Ahadi, A. Dehghan, Mohsen Mollahajiaghaei

Publication date: 21 March 2022

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

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$.

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

Recommendations

• Notes on simplicial rook graphs
• On the spectra of simplicial rook graphs
• scientific article; zbMATH DE number 2077666
• On the spectra of simplicial rook graphs
• scientific article; zbMATH DE number 1124599

zbMATH Keywords

computational complexityautomorphism groupindependence numbersimplicial rook graphcyclic simplicial rook graph

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Notes on simplicial rook graphs
• On the spectra of simplicial rook graphs
• Title not available (Why is that?)

Cited In (1)

• 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)