Chulalongkorn University Theses and Dissertations (Chula ETD)

Clique partitions of glued graphs

Other Title (Parallel Title in Other Language of ETD)

การแบ่งกั้นกราฟปะติดด้วยคลีก

Year (A.D.)

2009

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.2009.1195

Abstract

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 as the original graphs. A clique partition of a graph is a set of its cliques which together contain each edge exactly once. The clique partition number of a graph is the smallest cardinality of its clique partitions. We study bounds of clique partition numbers of glued graphs in terms of clique partition numbers of their original graphs. Also, we investigate values or bounds of clique partition numbers of clique-preserving glued graphs and glued graphs with specified clones such as complete graphs K2 and K3.

Other Abstract (Other language abstract of ETD)

กราฟปะติด คือ กราฟที่ได้จากการรวมกราฟสองกราฟที่ไม่มีจุดยอดร่วมกันโดยการปะติดจุดยอด และเส้นเชื่อมของกราฟย่อยเชื่อมโยงที่มีเส้นเชื่อมอย่างน้อยหนึ่งเส้นของทั้งสองกราฟนั้น เราเรียกกราฟย่อยที่กล่าวมาว่า กราฟโคลน และเรียกกราฟสองกราฟที่ไม่มีจุดยอดร่วมกันว่า กราฟต้นฉบับ ผลแบ่งกั้นกราฟด้วยคลีก คือ เซตของคลีกของกราฟ ซึ่งเส้นเชื่อมแต่ละเส้นเป็นเส้นเชื่อมของคลีกเหล่านั้นเพียงคลีกเดียวเท่านั้น จำนวนคลีกแบ่งกั้นกราฟ คือ จำนวนสมาชิกที่น้อยที่สุดของผลแบ่งกั้นกราฟด้วยคลีก งานวิจัยนี้เราศึกษาหาขอบเขตของจำนวนคลีกแบ่งกั้นกราฟของกราฟปะติดในพจน์ของจำนวนคลีกแบ่งกั้นกราฟของกราฟต้นฉบับ นอกจากนั้นเราหาค่าหรือขอบเขตของจำนวนคลีกแบ่งกั้นกราฟของกราฟปะติดคงสภาพคลีก และกราฟปะติดที่กำหนดกราฟโคลนของกราฟปะติดเป็น กราฟบริบูรณ์ที่มี 2 จุดยอดและกราฟบริบูรณ์ที่มี 3 จุดยอด

Link to Full Text

Share

COinS