Clique coverings and clique partitions of the K-power of graphs

Abstract

กำหนดให้ G เป็นกราฟใด ๆ การคลุมกราฟ G ด้วยคลิก คือ เซตของคลิกของ G ซึ่งเส้นเชื่อมแต่ละเส้นของ G เป็นเส้นเชื่อมของคลิกอย่างน้อยหนึ่งคลิก และเรียกจำนวนสมาชิกที่น้อยที่สุดของการคลุมกราฟ G ด้วยคลิกว่า จำนวนคลิกคลุมกราฟ G เขียนแทนด้วย cc(G) การแบ่งกั้นกราฟ G ด้วยคลิก คือ เซตของคลิกของ G ซึ่งเส้นเชื่อมแต่ละเส้นของ G เป็นเส้นเชื่อมของคลิกเพียงหนึ่งเท่านั้น และเรียกจำนวนสมาชิกที่น้อยที่สุดของการแบ่งกั้นกราฟ G ด้วยคลิกว่า จำนวนคลิกแบ่งกั้นกราฟ G เขียนแทนด้วย cp(G) กราฟกำลัง k ของกราฟ G เขียนแทนด้วย Gk คือกราฟที่มีเซตของจุดยอดเป็นเซตเดียวกับเซตของจุดยอดของ G และมีเส้นเชื่อมระหว่างจุดยอด u และ v ใน Gk ก็ต่อเมื่อมีวิถีที่มีความยาวไม่เกิน k ระหว่างจุดยอด u และ v ใน G เราหาค่าหรือขอบเขตของจำนวนคลิกคลุมกราฟ และจำนวนคลิกแบ่งกั้นกราฟของกราฟ กำลัง k ของ กราฟวิถี กราฟวัฏจักร กราฟพีระมิด กราฟบันได และกราฟตาราง