Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
ตำรวจและโจรบนไฮเพอร์กราฟ
Year (A.D.)
2020
Document Type
Thesis
First Advisor
Ratinan Boonklurb
Second Advisor
Sirirat Singhun
Faculty/College
Faculty of Science (คณะวิทยาศาสตร์)
Department (if any)
Department of Mathematics and Computer Science (ภาควิชาคณิตศาสตร์และวิทยาการคอมพิวเตอร์)
Degree Name
Doctor of Philosophy
Degree Level
Doctoral Degree
Degree Discipline
Mathematics
DOI
10.58837/CHULA.THE.2020.296
Abstract
Cops and robbers game is a game usually played on a finite connected graphwith two players, cop and robber. Recently, cops and robbers game played on hypergraphs was introduced. To give a better chance to a cop by allowing morethan one cop and at least one cop has to move, the cop-number, the least numberof cops to guarantee that they win the game, on graphs and hypergraphs is studied.This thesis provides (i) a characterization of a cop-win hypergraph (ii) some results on the products of hypergraphs and (iii) the cop-number of complete k-partite hypergraphs and n-prisms over a hypergraph. Moreover, the cop-number of a special class of graphs is determined.
Other Abstract (Other language abstract of ETD)
ตํารวจ และ โจร เป็น เกม ที่ นิยม เล่น บน กราฟ เชื่อม โยง จํากัด ประกอบ ด้วย ผู้ เล่น สอง คน ได้แก่ ตํารวจ และ โจร ปัจจุบันนี้ มีการแนะนําตํารวจและโจรบนไฮเพอร์กราฟ การให้โอกาสที่ดีกว่า แก่ตํารวจโดยการอนุญาตให้มีตํารวจมากกว่าหนึ่งคน และตํารวจอย่างน้อยหนึ่งคนต้องเดิน ส่งผลให้เกิดการศึกษาจํานวนตํารวจซึ่งคือจํานวนตํารวจที่น้อยที่สุดที่รับประกันว่าพวกเขาจะชนะเกมนี้บนกราฟและไฮเพอร์กราฟ วิทยานิพนธ์นี้ให้ (i) ลักษณะเฉพาะของไฮเพอร์กราฟที่ตํารวจชนะ(ii) ผลของผลคูณของไฮเพอร์กราฟ และ (iii) จํานวนตํารวจของไฮเพอร์กราฟ k ส่วนบริบูรณ์และ n-ปริซึมของไฮเพอร์กราฟ ยิ่งไปกว่านั้นยังได้กําหนดจํานวนตํารวจของกราฟประเภทพิเศษ
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
Siriwong, Pinkaew, "Cops and robbers on hypergraphs" (2020). Chulalongkorn University Theses and Dissertations (Chula ETD). 354.
https://digital.car.chula.ac.th/chulaetd/354