GAME DOMINATION NUMBERS OF COMPLETE MULTIPARTITE GRAPHSAND EXTENDED STAR GRAPHS.

Abstract

A simple graph G consists of a set of vertices and a set of edges connecting between two vertices. In the study of domination on a graph, vertices on the graph are selected; the selected vertices and all vertices that have edges connected to the selected vertices are considered dominated. A vertex can be selected if selecting it results in at least one new vertex being dominated. The smallest number of selected vertices so that every vertex on G is dominated is called the domination number of G, denoted by γ (G). It was later adapted to a mathematical game called domination game, where two players take turns picking one vertex at a time to dominate the vertices in the same graph, and the game ends when all the vertices on the graph are dominated. Each player has different goals, one player chooses vertices to end the game as quickly as possible; this player is called Dominator. The other player's goal is for the game to end as late as possible; this player is called Staller. Domination game differs from regular games which have results in loss, win or draw. The domination game will not have winners, but it focuses on the study of the best playing strategies of each player. Who starts the game may affect the number of moves to finish a game, so the game is divided into two types: game started by Dominator and game started by Staller. The number of moves to finish the game on when both players use optimal strategies is the game domination number of G, where γg (G) represents the game domination number when Dominator starts the game and γg'(G) represents the game domination number when the Staller starts the game. In this thesis, we are interested in studying the complete multipartite graphs, the extended star graphs Sk2 and Sk3 to find their domination numbers and game domination numbers.

กราฟอย่างง่าย G ประกอบด้วยเซตของจุด V และ เซตของเส้น E ที่เชื่อมต่อระหว่างจุดสองจุด ในการศึกษาจำนวนโดมิเนชันของกราฟ G จะมีการเลือกจุดบนกราฟโดยจุดที่ถูกเลือกและจุดทุกจุดที่มีเส้นเชื่อมกับจุดที่ถูกเลือกดังกล่าว จะถือว่าเป็นจุดที่ถูกครอบคลุม ซึ่งในการเลือกจุดแต่ละครั้งนั้นอาจเลือกจุดที่ถูกครอบคลุมแล้วหรือจุดที่ยังไม่ถูกครอบคลุมก็ได้ แต่จะต้องเกิดการครอบคลุมเพิ่มขึ้นอย่างน้อยหนึ่งจุด และเรียกจำนวนครั้งที่น้อยที่สุดในการเลือกจุดเพื่อให้ทุกจุดบน G ถูกครอบคลุมว่าจำนวนโดมิเนชันของ G เขียนแทนด้วย γg(G) ต่อมามีการดัดแปลงให้เป็นเกมทางคณิตศาสตร์ที่เรียกว่าเกมโดมิเนชัน โดยมีผู้เล่นสองฝ่ายผลัดกันเลือกจุดครั้งละ 1 จุด เพื่อครอบคลุมจุดบนกราฟเดียวกัน และเกมจะสิ้นสุดเมื่อจุดทุกจุดบนกราฟถูกครอบคลุม ในการเล่นผู้เล่นแต่ละฝ่ายมีเป้าหมายต่างกัน ฝ่ายหนึ่งเลือกจุดเพื่อให้เกมสิ้นสุดเร็วที่สุดเรียกผู้เล่นนี้ว่าโดมิเนเตอร์ ผู้เล่นอีกฝ่ายมีเป้าหมายคือการเล่นเพื่อให้เกมสิ้นสุดช้าที่สุดเรียกผู้เล่นนี้ว่าสตอลเลอร์ เกมโดมิเนชันจะแตกต่างจากเกมทั่วไป ซึ่งมีผลลัพธ์คือ แพ้ ชนะ หรือเสมอ เกมโดมิเนชันจะไม่มีการตัดสินผลแพ้ชนะของผู้เล่น แต่จะเน้นการศึกษาถึงกลยุทธการเล่นที่ดีที่สุดของผู้เล่นแต่ละคน เนื่องจากการเริ่มเล่นก่อนหรือหลัง อาจมีผลต่อจำนวนครั้งในการเล่นเกม ดังนั้นในการศึกษาจึงแบ่งเกมออกเป็นสองลักษณะคือ เกมที่โดมิเนเตอร์เป็นฝ่ายเล่นก่อน กับเกมที่สตอลเลอร์เป็นฝ่ายเล่นก่อน และเรียกจำนวนครั้งในการเลือกจุดบน G เมื่อผู้เล่นทั้งสองฝ่ายเล่นดีที่สุดเพื่อให้ทุกจุดบน G ถูกครอบคลุมว่า จำนวนเกมโดมิเนชันของ G โดย γg(G) แทนจำนวนเกมโดมิเนชันของ G เมื่อโดมิเนเตอร์เป็นฝ่ายเล่นก่อน และ γg'(G) แทนจำนวนเกมโดมิเนชันของ G เมื่อสตอลเลอร์เป็นฝ่ายเล่นก่อน วิทยานิพนธ์นี้ผู้วิจัยสนใจที่จะศึกษากราฟหลายส่วนบริบูรณ์ กราฟดาวขยาย Sk2 และ Sk3เพื่อหารูปทั่วไปของจำนวนโดมิเนชันและจำนวนเกมโดมิเนชันของกราฟดังกล่าวให้เป็นประโยชน์ต่อผู้ที่ต้องการศึกษาต่อไป