สมบัติของกราฟ 3-i-vertex-critical

Abstract

กำหนดให้ i(G) แทนขนาดของเซตควบคุมอิสระที่เล็กที่สุดของกราฟ G เราจะเรียก กราฟ G ว่า n-i-vertex-critical เมื่อ i(G) = n และ i(G – v) < i(G) สำหรับแต่ละจุด v ∈ V(G) การจับคู่ M ใน G เรียกว่า การจับคู่สมบูรณ์ ถ้าทุกจุดในกราฟ G ตกกระทบกับบางเส้น ใน M ในวิทยานิพนธ์นี้เราได้ให้ลักษณะเฉพาะเจาะจงของกราฟเชื่อมโยง 3-i-vertex-critical ที่มี S เป็นเซตตัด โดยที่ 1≤ |S| ≤ 2 และให้สมบัติของกราฟ G ที่เป็นกราฟ 3-i-vertex-critical ที่มี S เป็นเซตตัดขนาดเล็กสุด โดยที่ ΔG([S]) ≤ 1 ในเทอมของ ω(G – S) ยิ่งไปกว่านั้นเราแสดงว่า ω(G – S) ≤ |S| - 1 สำหรับเงื่อนไขบน S บางประการและสุดท้ายเราให้เงื่อนไขที่เพียงพอสำหรับ กราฟ 3-i-vertex-critical อันดับคู่ที่มีการจับคู่สมบูรณ์

Let i(G) denote the independent domination number of a graph G. A graph G is said to be n-i-vertex-critical if i(G) = n and i(G-v) < i(G) for all v∈V(G). A matching M in G is called a perfect matching if all vertices of G are incident with some edge of M. In this thesis, we provide characterizations of connected 3-i-vertex-critical graphs with a cutset S for 1 ≤ |S| ≤ 2. In addition, we present properties of 3-i-vertex-critical graphs G with a minimum cutset S where Δ(G[S]) ≤ 1 in terms of ω(G-S). Moreover, we show that ω(G - S) ≤ |S| - 1 with some condition on |S|. Finally, we provide a sufficient condition for 3-i-vertex-critical graphs of even order to have a perfect matching.