Chulalongkorn University Theses and Dissertations (Chula ETD)
Perfection of glued graphs of perfect original graphs
Other Title (Parallel Title in Other Language of ETD)
ความสมบูรณ์ของกราฟปะติดซึ่งกราฟต้นฉบับสมบูรณ์
Year (A.D.)
2008
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.2008.1122
Abstract
A graph G is perfect if the chromatic number and the clique number have the same value for every of its induced subgraph. 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. The main results involve in the perfection of glued graphs whose original graphs are perfect. We find necessary and/or sufficient conditions for the perfections of glued graphs. We also study the chromatic number and the clique numbers of glued graphs in terms of these parameters of their original graphs. Only some specified clones and original graphs are investigated:- clones such as induced subgraphs of both original graphs and complete graphs; original graphs such as bipartite graphs, complete graphs and forests.
Other Abstract (Other language abstract of ETD)
กราฟ G เป็น กราฟสมบูรณ์ ก็ต่อเมื่อ ทุกๆ กราฟย่อยชักนำของ G มีรงคเลขและจำนวนคลีกเท่ากัน กราฟปะติด คือกราฟที่ได้จากการรวมกราฟสองกราฟที่ไม่มีจุดยอดร่วมกันโดยการปะติดจุดยอดและเส้นเชื่อมของกราฟย่อยเชื่อมโยงที่มีเส้นเชื่อมอย่างน้อยหนึ่งเส้นของทั้งสองกราฟนั้น ซึ่งเรียกกราฟย่อยที่กล่าวมาว่า กราฟโคลน และเรียกกราฟสองกราฟที่ไม่มีจุดยอดร่วมกันว่า กราฟต้นฉบับ ผลลัพท์หลักเกี่ยวข้องกับความสมบูรณ์ของกราฟปะติดเมื่อกราฟต้นฉบับเป็นกราฟสมบูรณ์ เราหาเงื่อนไขจำเป็นและหรือเงื่อนไขเพียงพอสำหรับความสมบูรณ์ของกราฟปะติด นอกจากนั้นเราศึกษารงคเลขและจำนวนคลีกของกราฟปะติดในพจน์ของตัวแปรเหล่านี้ของกราฟต้นฉบับ เราสนใจเฉพาะกราฟโคลนของกราฟปะติด เช่นกราฟสองส่วน กราฟบริบูรณ์ หรือกราฟป่าไม้
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
Saduakdee, Supaporn, "Perfection of glued graphs of perfect original graphs" (2008). Chulalongkorn University Theses and Dissertations (Chula ETD). 58575.
https://digital.car.chula.ac.th/chulaetd/58575