We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
On the Maximum Number of Non-attacking Rooks on a High-Dimensional Simplicial Chessboard.
- Authors
Ahadi, Arash; Mollahajiaghaei, Mohsen; Dehghan, Ali
- Abstract
The simplicial rook graph SR (m , n) is the graph whose vertices are vectors in 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 31:1589–1611, 2015) asked about the independence number of SR (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 α (SR (m , n)) = (1 - o (1)) n + m - 1 n m . We also prove that for the domination number of rook graphs we have γ (SR (m , n)) = Θ (n m - 2) . Moreover we show that these graphs are Hamiltonian. The cyclic simplicial rook graph CSR (m , n) is the graph whose vertices are vectors in 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 CSR (m , n) is NP -hard in terms of n and m.
- Subjects
AUTOMORPHISM groups; HAMILTONIAN graph theory; CHARTS, diagrams, etc.; SOCIAL responsibility of business; PROBLEM solving
- Publication
Graphs & Combinatorics, 2022, Vol 38, Issue 3, p1
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-022-02456-4