ในทฤษฎีกราฟ เซต ครอบงำอิสระสำหรับกราฟ${\displaystyle G=(V,E)}$เป็นเซตย่อย${\displaystyle D\subseteq V}$ที่ครอบงำเซตอิสระที่กำหนด${\displaystyle A}$ของ${\displaystyle G}$นั่นคือ ทุกจุดยอดใน${\displaystyle A}$อยู่ใน${\displaystyle D}$หรืออยู่ติดกับจุดยอดใน${\displaystyle D}$[ ^{1 ]} ต่างจาก เซตครอบงำทั่วไปซึ่งต้องครอบงำทุกจุดยอดในกราฟ เซตครอบงำอิสระจำเป็นต้องครอบงำเฉพาะจุดยอดของเซตอิสระเฉพาะ^{เท่านั้น}

หมายเลขการครอบงำความเป็นอิสระ${\displaystyle i\gamma (G)}$ของกราฟ${\displaystyle G}$คือค่าสูงสุด เหนือเซตอิสระทั้งหมด${\displaystyle A}$ของ${\displaystyle G}$ของเซตที่เล็กที่สุดที่ครอบงำ${\displaystyle A}$[ ^{1 ]}การครอบงำกลุ่มย่อยของจุดยอดอาจต้องใช้จุดยอดน้อยกว่าการครอบงำจุดยอดทั้งหมด^{ดังนั้น}${\displaystyle i\gamma (G)\leq \gamma (G)}$สำหรับกราฟทั้งหมด${\displaystyle G}$.

ความไม่เท่าเทียมกันอาจเป็นแบบเข้มงวด มีกราฟอยู่ด้วย${\displaystyle G}$ซึ่ง${\displaystyle i\gamma (G)<\gamma (G)}$ตัวอย่างเช่น สำหรับจำนวนเต็มบางจำนวน${\displaystyle n}$, อนุญาต${\displaystyle G}$เป็นกราฟที่จุดยอดเป็นแถวและคอลัมน์ของ${\displaystyle n}$-โดย-${\displaystyle n}$กระดาน และจุดยอดสองจุดดังกล่าวจะเชื่อมต่อกันก็ต่อเมื่อจุดยอดทั้งสองตัดกันเท่านั้น เซตอิสระเพียงอย่างเดียวคือเซตของแถวเท่านั้นหรือเซตของคอลัมน์เท่านั้น และแต่ละเซตสามารถถูกครอบงำโดยจุดยอดเพียงจุดเดียว (คอลัมน์หรือแถว) ดังนั้น${\displaystyle i\gamma (G)=1}$อย่างไรก็ตาม เพื่อให้ครอบคลุมทุกจุดยอด เราจำเป็นต้องมีอย่างน้อยหนึ่งแถวและหนึ่งคอลัมน์ ดังนั้น${\displaystyle \gamma (G)=2}$นอกจากนี้ อัตราส่วนระหว่าง${\displaystyle \gamma (G)/i\gamma (G)}$สามารถมีขนาดใหญ่ได้ตามอำเภอใจ ตัวอย่างเช่น ถ้าจุดยอดของ${\displaystyle G}$เซตย่อยทั้งหมดของกำลังสองของ${\displaystyle n}$-โดย-${\displaystyle n}$กระดาน จากนั้นก็ยังคงอยู่${\displaystyle i\gamma (G)=1}$, แต่${\displaystyle \gamma (G)=n}$[ ^{1 ]​}

จำนวนการครอบงำที่เป็นอิสระมีความเชื่อมโยงอย่างใกล้ชิดกับสมมติฐานของวิซิงซึ่งระบุว่าสำหรับกราฟทั้งหมด${\displaystyle G}$และ${\displaystyle H}$จำนวนการครอบงำของผลคูณคาร์ทีเซียนเป็นไปตามเงื่อนไข${\displaystyle \gamma (G\mathbin {\square } H)\geq \gamma (G)\cdot \gamma (H)}$[ ^{2 ] Aharoni}และ Szabó แสดงให้เห็นว่าสำหรับกราฟทั้งหมด${\displaystyle G}$และ${\displaystyle H}$[ ^{3 ]​}

${\displaystyle \gamma (G\mathbin {\square } H)\geq i\gamma (G)\cdot \gamma (H)}$

${\displaystyle i\gamma (G\mathbin {\square } H)\geq i\gamma (G)\cdot i\gamma (H)}$

เนื่องจากคลาสกราฟใดๆ สำหรับซึ่ง${\displaystyle \gamma (G)=i\gamma (G)}$เป็นไปตามสมมติฐานของ Vizing โดยอัตโนมัติ การเชื่อมต่อนี้กระตุ้นให้เกิดการศึกษาว่าคลาสกราฟใดมีคุณสมบัตินี้^{[ 2 ]}

สำหรับกราฟคอร์ดัลจำนวนการครอบงำแบบอิสระจะเท่ากับจำนวนการครอบงำ:${\displaystyle \gamma (G)=i\gamma (G)}$[ ^{1 ]}ซึ่งหมายความว่าสมมติฐานของ Vizing เป็นจริงสำหรับกราฟคอร์ดัล^{[ 3 ]}สำหรับกราฟคอร์ดัลที่แข็งแกร่ง ความเท่าเทียมกันเดียวกันนี้เป็นจริง เนื่องจากจำนวนการ ^{ครอบงำ}เศษส่วนเท่ากับจำนวนการครอบงำสำหรับกราฟดังกล่าว^{[ 2 ]}

สำหรับกราฟโคกราฟจำนวนการครอบงำแบบอิสระมีลักษณะเฉพาะที่เรียบง่าย:${\displaystyle i\gamma (G)}$เท่ากับจำนวนส่วนประกอบที่เชื่อมต่อกันของ${\displaystyle G}$[ ^{2 ]}สิ่งนี้เป็นผลมาจากโครงสร้างแบบเรียกซ้ำของโคกราฟในฐานะการเชื่อมต่อและการรวมกัน: ในการเชื่อม^ต่อ${\displaystyle G_{1}\otimes G_{2}}$เซตอิสระสูงสุดใดๆ จะบรรจุอยู่ในองค์ประกอบหนึ่ง และสามารถถูกครอบงำโดยจุดยอดเดียวจากองค์ประกอบอื่นได้ ทำให้ได้${\displaystyle i\gamma (G)=1}$ในสหภาพ${\displaystyle G_{1}\oplus G_{2}}$ตัวเลขการครอบงำความเป็นอิสระจะรวมกัน^{[ 2 ]}

การคำนวณจำนวนการครอบงำแบบอิสระเป็นปัญหา NP-completeสำหรับกราฟหลายประเภท รวมถึงกราฟคอร์ดัล (เนื่องจากการครอบงำเป็นปัญหา NP-complete อยู่แล้วสำหรับกราฟคอร์ดัล) และกราฟสองส่วนนอกจากนี้ การตัดสินใจว่า... ก็เป็นปัญหา NP-complete เช่นกัน${\displaystyle i\gamma (G)\geq 2}$สำหรับ^กราฟคอร์ดอ่อน [ ^{4 ]}

ในทางกลับกัน อัลกอริทึมเวลาพหุนามมีอยู่สำหรับคลาสกราฟที่จำกัดบางคลาส: ^{[ 2 ]}

• กราฟคอร์ดที่แข็งแกร่ง
• กราฟที่สืบทอดระยะทาง (และโดยทั่วไป กราฟที่มีความกว้างอันดับ จำกัด ) ใน${\displaystyle O(n^{3})}$เวลา
• กราฟการเรียงสับเปลี่ยนในเวลาพหุนาม
• กราฟของtreewidth ที่มีขอบเขต ใน${\displaystyle O(n^{3})}$เวลา

สำหรับกราฟทั่วไป มีอัลกอริธึมที่แม่นยำซึ่งใช้เวลาในการประมวลผลแบบเลขชี้กำลัง${\displaystyle O^{*}(1.7972^{n})}$เวลา อัลกอริทึมนี้จะแจงนับเซตอิสระสูงสุด ทั้งหมด (ซึ่งมีอย่างมากที่สุด)${\displaystyle 3^{n/3}}$โดยขอบเขต Moon–Moser ) และค้นหาเซตครอบงำขั้นต่ำสำหรับแต่ละรายการโดยใช้กลยุทธ์การแตกกิ่งรวมกับการจับคู่สูงสุด^{[ 2 ]}

จำนวนการครอบงำแบบอิสระสองฝ่าย${\displaystyle i\gamma i(G)}$ของกราฟ${\displaystyle G}$คือค่าสูงสุด เหนือเซตอิสระทั้งหมด${\displaystyle A}$ของ${\displaystyle G}$ของเซตอิสระที่เล็กที่สุดที่ครอบงำ${\displaystyle A}$ความสัมพันธ์ต่อไปนี้ใช้ได้กับกราฟใดๆ${\displaystyle G}$: $${\displaystyle {\begin{aligned}i(G)&\geq \gamma (G)\geq i\gamma (G)\\i(G)&\geq i\gamma i(G)\geq i\gamma (G)\end{aligned}}}$$ ที่ไหน${\displaystyle i(G)}$คือจำนวนการครอบงำที่เป็นอิสระ

• ชุดครอบงำอิสระ
• ข้อสันนิษฐานของวิซิง