文献

J-GLOBAL ID：202202270711319930   整理番号：22A0764311

高次元単体チェス盤上における攻撃しないルークの最大数について

On the Maximum Number of Non-attacking Rooks on a High-Dimensional Simplicial Chessboard

著者 (3件)： Ahadi Arash (Department of Mathematical and Computer Sciences, Kharazmi University, Tehran, Iran) ,  Mollahajiaghaei Mohsen (Department of Management and Organizational Studies, Huron University, London, Canada) ,  Dehghan Ali (Systems and Computer Engineering Department, Carleton University, Ottawa, Canada)
資料名： Graphs and Combinatorics (Web)  (Graphs and Combinatorics (Web))
巻： 38  号： 3  ページ： 52  発行年： 2022年 
JST資料番号： U1590A  ISSN： 0911-0119  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 単体ルークグラフSR(m,n)は頂点がN^m内のベクトルとなるグラフであり,ここで対応するベクトルが二つの座標で厳密に異なる場合に各ベクトルについてその座標の和がnとなりさらに二つの頂点が隣接している。MartinとWagner(Graphs Combin31:1589-1611,2015)は,一辺の長さがn+1の(m-1)次元単体チェス盤上に配置可能な攻撃しないルークの最大数であるSR(m,n)の独立数について質問した。本研究では,この問題を解決し,α(SR(m,n))=(1-ο(1))[数式:原文を参照]であることを示す。ルークグラフの支配数について,γ(SR(m,n))=Θ(n^m-2)を持つことも示す。さらに,これらのグラフがハミルトニアンであることも示す。循環単体ルークグラフCSR(m,n)はその頂点がZ^m_n内のベクトルとなるグラフであり,ここで対応するベクトルが二つの座標で厳密に異なる場合に各ベクトルについてその座標の和のモジュロnが0となりさらに二つの頂点が隣接している。本研究では,独立数,彩色数及び自己同形群等のようなこれらのグラフのいくつかの特性を決定する。その他の結果の中でも,与えられたCSR(m,n)の二つの頂点間の距離の計算がnとmに関してNP困難であることも証明した。Copyright The Author(s), under exclusive licence to Springer Japan KK, part of Springer Nature 2022 Translated from English into Japanese by JST.

シソーラス用語： *娯楽 ,  高次元 ,  *玩具 ,  頂点 ,  座標系 ,  ベクトル ,  配置 ,  独立性 ,  循環 ,  集合 ,  NP困難 ,  *グラフ理論 ,  群 ,  数値 ,  計算量
準シソーラス用語： NP困難性 ,  *チェス ,  *駒【ゲーム】 ,  計算複雑性 ,  座標システム ,  彩色数 ,  支配集合 ,  自己同形群 ,  隣接関係

著者キーワード (5件)： 単体ルックグラフ ,  環状単体Rookグラフ ,  独立数 ,  自己同形群 ,  計算の複雑さ

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (4件)： 高次元 ,  単体 ,  チェス ,  攻撃