Chulalongkorn University Theses and Dissertations (Chula ETD)

Title (Main Language of ETD)

Cops and robbers on hypergraphs

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-ปริซึมของไฮเพอร์กราฟ ยิ่งไปกว่านั้นยังได้กําหนดจํานวนตํารวจของกราฟประเภทพิเศษ

Download

Included in

Mathematics Commons

COinS