Biased Domination Games
Thesis (M.Sc., Mathematics)--Prince of Songkla University, 2022
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Theses and Dissertations |
| Language: | English |
| Published: |
Prince of Songkla University
2023
|
| Subjects: | |
| Online Access: | http://kb.psu.ac.th/psukb/handle/2016/18000 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Prince of Songkhla University |
| Language: | English |
| id |
th-psu.2016-18000 |
|---|---|
| record_format |
dspace |
| spelling |
th-psu.2016-180002023-04-19T08:11:47Z Biased Domination Games เกมไบแอสโดมิเนชัน Tharit Sereekiatdilok Panupong Vichitkunakorn Faculty of Science (Mathemetics and Statistics) คณะวิทยาศาสตร์ ภาควิชาคณิตศาสตร์และสถิติ biased domination game biased game domination number maximal move minimal move Numerical calculations Computer program Thesis (M.Sc., Mathematics)--Prince of Songkla University, 2022 A Domination game on a graph G is a game of two players, called Dominator and Staller, on a graph. The players take turns to perform a move by choosing a vertex in the graph. Vertices in the closed neighborhood of a chosen vertex are said to be dominated. A move u is legal if it creates at least one new dominated vertex. The game is ended when all vertices in the graph are dominated. Dominator tries to end the game as soon as possible, while Staller tries to prolong the game. In the domination game, if Dominator starts the game, this game is said to be Game 1. Otherwise, it is said to be Game 2. If both players play optimally in a domination game on a graph G, the number of moves when the game is ended is called the game domination numbers. In this research, we introduce an extended version of a domination game on a graph, called a biased domination game, in which Dominator and Staller play more than one move in each turn. Similarly, we define the biased game domination number as the number of moves in an ended biased domination game which both players play with optimal strategies. We study relations of biased game domination numbers between various games. In addition, we study two special types of moves, called minimal moves and maximal moves. Some properties of the biased game domination numbers on a graph where the special moves are always available is studied. Lastly, the biased game domination numbers of powers of a cycle are explicitly computed, together with optimal strategies using a special move. เกมโดมิเนชัน (domination game) บนกราฟ G เป็นเกมที่ประกอบไปด้วยผู้ เล่น 2 คน ได้แก่ โดมิเนเตอร์ (Dominator) และสตอลเลอร์ (Staller) โดยแต่ละตาผู้เล่นจะ ผลัดกันเลือกจุดหนึ่งจุดบนกราฟ G หลังจากนั้นจุดที่ถูกเลือกจะโดมิเนท (dominate) ย่านใกล้ เคียงปิด (closed neighborhood) ของจุดนั้น ในแต่ละตานั้นผู้เล่นจะต้องเลือกจุดที่โดมิเนท จุดเพิ่มขึ้นอย่างน้อยหนึ่งจุดเสมอ เกมจะจบลงเมื่อทุกจุดบนกราฟถูกโดมิเนท โดมิเนเตอร์จะ พยายามทําให้เกมจบด้วยการทําให้จํานวนครั้งในการเลือกจุดทั้งหมดน้อยที่สุด ในทางกลับกันส ตอลเลอร์จะพยายามยืดเกมให้ยาวนานที่สุดเท่าที่เป็นไปได้ เราจะเรียกเกมโดมิเนชันว่า เกมที่ 1 เมื่อโดมิเนเตอร์เป็นผู้เริ่มเกมและ เกมที่ 2 เมื่อสตอลเลอร์เป็นผู้เริ่มเกม ถ้าผู้เล่นทั้งคู่เล่นเกมโดย ใช้วิธีที่ดีที่สุดจนเกมจบแล้วจํานวนครั้งในการเลือกจุดทั้งหมดในเกมจะถูกเรียกว่า เลขเกมโดมิ เนชัน (game domination number) ในการศึกษาครั้งนี้ เราขอเสนอเกมไบแอสโดมิเนชัน (biased domination game) ที่อยู่ในรูปแบบที่ถูกขยายขึ้นจากเกมโดมิเนชัน โดยแต่ละตาผู้เล่นสามารถเลือกจุดได้ มากกว่าหนึ่งจุด ในทํานองเดียวกัน ถ้าผู้เล่นทั้งคู่เล่นเกมโดยใช้วิธีที่ดีที่สุดจนเกมจบแล้วจํานวน ครั้งในการเลือกจุดทั้งหมดในเกมจะถูกเรียกว่า เลขไบแอสเกมโดมิเนชัน (biased game domi- nation number) เราศึกษาความสัมพันธ์ของเลขไบแอสเกมโดมิเนชันของเกมไบแอสโดมิเนชัน ต่าง ๆ นอกจากนี้เรายังคํานวณเลขไบแแอสเกมโดมิเนชันบนบางกราฟ เช่น กราฟวัฏจักร (cy- cle) และกราฟกําลังของกราฟวัฏจักร (power of cycle) ยิ่งไปกว่านั้นเราศึกษาวิธีการการ เลือกจุดแบบพิเศษที่เรียกว่า การเลือกแบบมินิมอล (minimal move) และการเลือกแบบแมก ซิมอล (maximal move) ซึ่งเราหาสมบัติบางประการของเลขไบแอสเกมโดมิเนชันบนกราฟ ที่สามารถเลือกจุดเหล่านี้ได้ ท้ายที่สุดเราคํานวณค่าเลขไบแอสเกมโดมิเนชันบนกราฟกําลังของ กราฟวัฏจักร (power of cycle) และหาการเล่นที่เหมาะสมที่สุดโดยใช้การเลือกจุดแบบพิเศษ 2023-04-19T08:10:54Z 2023-04-19T08:10:54Z 2022 Thesis http://kb.psu.ac.th/psukb/handle/2016/18000 en Attribution-NonCommercial-NoDerivs 3.0 Thailand http://creativecommons.org/licenses/by-nc-nd/3.0/th/ application/pdf Prince of Songkla University |
| institution |
Prince of Songkhla University |
| building |
Khunying Long Athakravi Sunthorn Learning Resources Center |
| continent |
Asia |
| country |
Thailand Thailand |
| content_provider |
Khunying Long Athakravi Sunthorn Learning Resources Center |
| collection |
PSU Knowledge Bank |
| language |
English |
| topic |
biased domination game biased game domination number maximal move minimal move Numerical calculations Computer program |
| spellingShingle |
biased domination game biased game domination number maximal move minimal move Numerical calculations Computer program Tharit Sereekiatdilok Biased Domination Games |
| description |
Thesis (M.Sc., Mathematics)--Prince of Songkla University, 2022 |
| author2 |
Panupong Vichitkunakorn |
| author_facet |
Panupong Vichitkunakorn Tharit Sereekiatdilok |
| format |
Theses and Dissertations |
| author |
Tharit Sereekiatdilok |
| author_sort |
Tharit Sereekiatdilok |
| title |
Biased Domination Games |
| title_short |
Biased Domination Games |
| title_full |
Biased Domination Games |
| title_fullStr |
Biased Domination Games |
| title_full_unstemmed |
Biased Domination Games |
| title_sort |
biased domination games |
| publisher |
Prince of Songkla University |
| publishDate |
2023 |
| url |
http://kb.psu.ac.th/psukb/handle/2016/18000 |
| _version_ |
1764209943028695040 |