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

• Main Author: Tanawat Wichianpaisarn (Author)
• Other Authors: Chariya Uiyyasathian (Contributor), Chulalongkorn University. Faculty of Science (Contributor)
• Format: Book
• Published: Chulalongkorn University, 2014-03-25T12:38:30Z.
• Subjects: Thesis
• Online Access: Connect to this object online.

Summary

Thesis (M.Sc.)--Chulalongkorn University, 2007
กำหนดให้ 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 ของ กราฟวิถี กราฟวัฏจักร กราฟพีระมิด กราฟบันได และกราฟตาราง
Let G be any graph. A clique covering of G is a set of cliques of G, which together contain each edge of G at least once. The smallest cardinality of clique coverings of G is called the clique covering number of G, and is denoted by cc(G). A clique partition of G is a set of cliques of G, which together contain each edge of G exactly once. The smallest cardinality of clique partitions of G is called the clique partition number of G, and is denoted by cp(G). The graph Gk is the k-power of a graph G if V (Gk ) = V (G) and there is an edge between vertices u and v in Gk if and only if there is a path of length at most k between u and v in G. We investigate values or bound of the clique covering numbers and the clique partition numbers of the k-power of paths, cycles, pyramids, ladders and grids.