Chulalongkorn University Theses and Dissertations (Chula ETD)
Clique coverings of glued graphs
Other Title (Parallel Title in Other Language of ETD)
การคลุมกราฟปะติดด้วยคลิก
Year (A.D.)
2008
Document Type
Thesis
First Advisor
Chariya Uiyyasathian
Second Advisor
Wanida Hemakul
Faculty/College
Faculty of Science (คณะวิทยาศาสตร์)
Degree Name
Master of Science
Degree Level
Master's Degree
Degree Discipline
Mathematics
DOI
10.58837/CHULA.THE.2008.1112
Abstract
Let G be a graph. A clique covering of a graph G is a set of cliques of G in which each edge of G is contained in at least one clique. The clique covering number of G is the smallest cardinality of clique coverings of G. A glued graph results from combining two vertex-disjoint graphs by identifying nontrivial connected isomorphic subgraphs of both graphs. Such subgraphs are referred to as the clones. The two vertex-disjoint graphs are referred to the original graphs. We study bounds of clique covering numbers of glued graphs in terms of clique covering numbers of their original graphs. Also, we investigate values or bounds of clique covering numbers of glued graphs with specified clones such as a complete graph, a complete graph and an induced subgraph of both original graphs.
Other Abstract (Other language abstract of ETD)
ให้ G เป็นกราฟ การคลุมกราฟG ด้วยคลิก คือ เซตของคลิกของG ซึ่งเส้นเชื่อมแต่ละเส้นของ G เป็นเส้นเชื่อมของคลิกอย่างน้อยหนึ่งคลิก จำนวนคลิกคลุมกราฟG คือ จำนวนสมาชิกที่น้อยที่สุดของ การคลุมกราฟG ด้วยคลิก กราฟปะติด คือ กราฟที่ได้จากการรวมกราฟสองกราฟที่ไม่มีจุดยอดร่วมกันโดยการปะติดจุดยอด และ เส้นเชื่อมของกราฟย่อยเชื่อมโยงที่มีเส้นเชื่อมอย่างน้อยหนึ่งเส้นของทั้งสองกราฟนั้น ซึ่งเรียกกราฟย่อยที่กล่าวมาว่า กราฟโคลน และเรียกกราฟสองกราฟที่ไม่มีจุดยอดร่วมกันว่า กราฟต้นฉบับ เราศึกษาหาขอบเขตของจำนวนคลิกคลุมกราฟของกราฟปะติดในพจน์ของจำนวนคลิกคลุมกราฟ ของกราฟต้นฉบับ นอกจากนั้น เราหาค่าหรือขอบเขตของจำนวนคลิกคลุมกราฟของกราฟปะติด โดยกำหนด กราฟโคลนของกราฟปะติด คือ กราฟบริบูรณ์ กราฟบริบูรณ์ และกราฟย่อยชักนำของกราฟต้นฉบับ ทั้งสอง
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
Pimpasalee, Wannapol, "Clique coverings of glued graphs" (2008). Chulalongkorn University Theses and Dissertations (Chula ETD). 58565.
https://digital.car.chula.ac.th/chulaetd/58565