Perfection of glued graphs of perfect original graphs
Typescript (M.Sc.)--Chulalongkorn University, 2008
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Theses and Dissertations |
| Language: | English |
| Published: |
Chulalongkorn University
2011
|
| Subjects: | |
| Online Access: | http://cuir.car.chula.ac.th/handle/123456789/15908 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Chulalongkorn University |
| Language: | English |
| id |
th-cuir.15908 |
|---|---|
| record_format |
dspace |
| spelling |
th-cuir.159082011-09-21T03:57:27Z Perfection of glued graphs of perfect original graphs ความสมบูรณ์ของกราฟปะติดซึ่งกราฟต้นฉบับสมบูรณ์ Supaporn Saduakdee Chariya Uiyyasathian Chulalongkorn University. Faculty of Science Graphic methods Perfect graphs Graph theory Typescript (M.Sc.)--Chulalongkorn University, 2008 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. กราฟ G เป็น กราฟสมบูรณ์ ก็ต่อเมื่อ ทุกๆ กราฟย่อยชักนำของ G มีรงคเลขและจำนวนคลีกเท่ากัน กราฟปะติด คือกราฟที่ได้จากการรวมกราฟสองกราฟที่ไม่มีจุดยอดร่วมกันโดยการปะติดจุดยอดและเส้นเชื่อมของกราฟย่อยเชื่อมโยงที่มีเส้นเชื่อมอย่างน้อยหนึ่งเส้นของทั้งสองกราฟนั้น ซึ่งเรียกกราฟย่อยที่กล่าวมาว่า กราฟโคลน และเรียกกราฟสองกราฟที่ไม่มีจุดยอดร่วมกันว่า กราฟต้นฉบับ ผลลัพท์หลักเกี่ยวข้องกับความสมบูรณ์ของกราฟปะติดเมื่อกราฟต้นฉบับเป็นกราฟสมบูรณ์ เราหาเงื่อนไขจำเป็นและหรือเงื่อนไขเพียงพอสำหรับความสมบูรณ์ของกราฟปะติด นอกจากนั้นเราศึกษารงคเลขและจำนวนคลีกของกราฟปะติดในพจน์ของตัวแปรเหล่านี้ของกราฟต้นฉบับ เราสนใจเฉพาะกราฟโคลนของกราฟปะติด เช่นกราฟสองส่วน กราฟบริบูรณ์ หรือกราฟป่าไม้ 2011-09-21T03:57:26Z 2011-09-21T03:57:26Z 2008 Thesis http://cuir.car.chula.ac.th/handle/123456789/15908 en Chulalongkorn University 797201 bytes application/pdf application/pdf Chulalongkorn University |
| institution |
Chulalongkorn University |
| building |
Chulalongkorn University Library |
| country |
Thailand |
| collection |
Chulalongkorn University Intellectual Repository |
| language |
English |
| topic |
Graphic methods Perfect graphs Graph theory |
| spellingShingle |
Graphic methods Perfect graphs Graph theory Supaporn Saduakdee Perfection of glued graphs of perfect original graphs |
| description |
Typescript (M.Sc.)--Chulalongkorn University, 2008 |
| author2 |
Chariya Uiyyasathian |
| author_facet |
Chariya Uiyyasathian Supaporn Saduakdee |
| format |
Theses and Dissertations |
| author |
Supaporn Saduakdee |
| author_sort |
Supaporn Saduakdee |
| title |
Perfection of glued graphs of perfect original graphs |
| title_short |
Perfection of glued graphs of perfect original graphs |
| title_full |
Perfection of glued graphs of perfect original graphs |
| title_fullStr |
Perfection of glued graphs of perfect original graphs |
| title_full_unstemmed |
Perfection of glued graphs of perfect original graphs |
| title_sort |
perfection of glued graphs of perfect original graphs |
| publisher |
Chulalongkorn University |
| publishDate |
2011 |
| url |
http://cuir.car.chula.ac.th/handle/123456789/15908 |
| _version_ |
1681408834231336960 |