สมบัติการจับคู่บางประการในกราฟปริซึมเติมเต็ม

Abstract

ให้ แทนกราฟเติมเต็มของกราฟ G กราฟปริซึมเติมเต็มของกราฟ G เขียนแทนด้วย สามารถสร้างได้จากกราฟ G และกราฟ โดยเชื่อมจุดที่สมนัยกันด้วยเส้นเชื่อม จะกล่าวว่า กราฟเชื่อมโยง G ที่มีอันดับอย่างน้อย 2k+2 มีการขยายการจับคู่ขนาด k ถ้าทุก ๆ การจับคู่ M ขนาด k ในกราฟ G มีการจับคู่สมบูรณ์ใน G ที่มี M เป็ นสับเซต ในวิทยานิพนธ์นี้ เราศึกษาเงื่อนไขเพียงพอบางประการที่ทา ให้กราฟปริซึมเติมเต็มของ กราฟปรกติมีการขยายการจับคู่ขนาด 2 เรายังแสดงว่าส าหรับจา นวนเต็ม l1 และ l2 จะมีกราฟ G ที่ ไม่ใช่กราฟสองส่วนซึ่ง G มีการขยายการจับคู่ขนาด l1 และ มีการขยายการจับคู่ขนาด l2 และ ท้ายสุด เราแสดงว่า ถ้า G มีการขยายการจับคู่ขนาด l1 และ มีการขยายการจับคู่ขนาด l2 โดยที่ G และ ไม่ใช่กราฟสองส่วน ส าหรับ l1  2 และ l2  2 แล้ว มีการขยายการจับคู่ขนาด l+1 เมื่อ l = min{l1, l2}

Let denote the complement of a simple graph G. The complementary prism of G denoted by can be obtained by taking a copy of G and a copy of and then joining corresponding vertices by an edge. A connected graph G of order at least 2k+2 is k-extendable if for every matching M of size k in G, there is a perfect matching in G containing all edges of M. In this thesis, we establish some sufficient conditions for the complementary prism of regular graphs to be 2-extendable. We also show that for positive integers l1 and l2, there exists a non-bipartite graph G such that G is l1-extendable and is l2-extendable. Finally, we show that if G is l1-extendable and is l2-extendable non-bipartite graphs for l1  2 and l2  2, then is (l+1)-extendable where l = min{l1, l2}.