Chulalongkorn University Theses and Dissertations (Chula ETD)

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

Other Title (Parallel Title in Other Language of ETD)

การคลุมและการแบ่งกั้นกราฟกำลัง K ด้วยคลิก

Year (A.D.)

2007

Document Type

Thesis

First Advisor

Chariya Uiyyasathian

Faculty/College

Faculty of Science (คณะวิทยาศาสตร์)

Degree Name

Master of Science

Degree Level

Master's Degree

Degree Discipline

Mathematics

DOI

10.58837/CHULA.THE.2007.1070

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 ของ กราฟวิถี กราฟวัฏจักร กราฟพีระมิด กราฟบันได และกราฟตาราง

Other Abstract (Other language abstract of ETD)

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.

Link to Full Text

Share

COinS