ในทฤษฎีกราฟเซตครอบงำสำหรับกราฟGคือเซตย่อยDของจุดยอดของกราฟ G โดยที่จุดยอดใดๆ ของGจะต้องอยู่ในDหรือมีจุดยอดข้างเคียงอยู่ในDจำนวนครอบงำγ( G )คือจำนวนจุดยอดในเซตครอบงำที่เล็กที่สุดสำหรับ G

ปัญหาชุดครอบงำเกี่ยวข้องกับการทดสอบว่าγ( G ) ≤ KสำหรับกราฟG ที่กำหนด และอินพุตKหรือไม่ ซึ่งเป็นปัญหาการตัดสินใจ แบบ NP-complete คลาสสิก ในทฤษฎีความซับซ้อนของการคำนวณ [ ^{1 ] ดังนั้น}จึงเชื่อกันว่าอาจไม่มีอัลกอริทึมที่มีประสิทธิภาพที่สามารถคำนวณγ( G )สำหรับกราฟG ทั้งหมด ได้ อย่างไรก็ตาม มีอัลกอริทึมการประมาณค่า ที่มีประสิทธิภาพ เช่นเดียวกับอัลกอริทึมที่แม่นยำที่มีประสิทธิภาพสำหรับกราฟบางคลาส

ชุดครอบงำ (Dominating sets) มีประโยชน์ในทางปฏิบัติหลายด้าน ในเครือข่ายไร้สายชุดครอบงำถูกใช้เพื่อค้นหาเส้นทางที่มีประสิทธิภาพภายในเครือข่ายเคลื่อนที่แบบเฉพาะกิจ นอกจากนี้ยังมีการใช้ในงานสรุปเอกสารและในการออกแบบระบบรักษาความปลอดภัยสำหรับโครงข่ายไฟฟ้าอีก ด้วย

เซตครอบงำมีความสัมพันธ์อย่างใกล้ชิดกับเซตอิสระกล่าวคือ เซตอิสระจะเป็นเซตครอบงำก็ต่อเมื่อมันเป็นเซตอิสระสูงสุดดังนั้น เซตอิสระสูงสุดใดๆ ในกราฟจึงจำเป็นต้องเป็นเซตครอบงำขั้นต่ำด้วย

กำหนดให้กราฟแบบไม่มีทิศทางG = ( V , E )เซตย่อยของจุดยอดเรียกว่าเซตครอบงำถ้าสำหรับทุกจุดยอด V จะมีจุดยอด E ที่ทำให้ V = V + E ... ${\displaystyle D\subseteq V}$${\displaystyle u\in V\setminus D}$${\displaystyle v\in D}$${\displaystyle \{u,v\}\in E}$

กราฟทุกกราฟมีเซตครอบงำอย่างน้อยหนึ่งเซต: ถ้าเซตของจุดยอดทั้งหมดคือเซตของจุดยอดทั้งหมดแล้ว ตามคำนิยามDก็คือเซตครอบงำ เนื่องจากไม่มีจุดยอดใดที่ไม่เป็นเซตของจุดยอดทั้งหมด ความท้าทายที่น่าสนใจกว่าคือการหาเซตครอบงำขนาดเล็กจำนวนการครอบงำของ กราฟ Gถูกกำหนดดังนี้ : ${\displaystyle D=V=}$${\displaystyle u\in V\setminus D}$${\displaystyle \gamma (G):=\min\{|D|:D{\text{ เป็นเซตครอบงำของ }}G\}}$

ปัญหาการครอบงำได้รับการศึกษาตั้งแต่ช่วงทศวรรษ 1950 เป็นต้นมา แต่การวิจัยเกี่ยวกับการครอบงำเพิ่มขึ้นอย่างมีนัยสำคัญในช่วงกลางทศวรรษ 1970 ในปี 1972 Richard Karpได้พิสูจน์ว่าปัญหาการครอบคลุมเซตเป็น ปัญหา NP-completeซึ่งส่งผลโดยตรงต่อปัญหาเซตครอบงำ เนื่องจากมีการจับคู่แบบหนึ่งต่อหนึ่งระหว่างจุดยอดกับเซตและขอบกับจุดตัดที่ไม่แยกจากกันโดยตรงระหว่างสองปัญหานี้ ซึ่งพิสูจน์ได้ว่าปัญหาเซตครอบงำเป็นปัญหาNP-completeเช่นกัน^{[ 2 ]}

ปัญหาการครอบคลุมเซตเป็น ปัญหา NP-hard ที่รู้จักกันดี – เวอร์ชันการตัดสินใจของการครอบคลุมเซตเป็นหนึ่งใน21 ปัญหา NP-complete ของ Karpมีการลดรูป L-reduction ในเวลาพหุนามคู่หนึ่ง ระหว่างปัญหาเซตครอบงำขั้นต่ำและปัญหาการครอบคลุมเซต^{[ 3 ]}การลดรูปเหล่านี้ ( ดูด้านล่าง ) แสดงให้เห็นว่าอัลกอริทึมที่มีประสิทธิภาพสำหรับปัญหาเซตครอบงำขั้นต่ำจะให้อัลกอริทึมที่มีประสิทธิภาพสำหรับปัญหาการครอบคลุมเซต และในทางกลับกัน ยิ่งไปกว่านั้น การลดรูปยังคงรักษาอัตราส่วนการประมาณค่าไว้ : สำหรับ α ใดๆ อั ลกอริ ทึมการประมาณค่า α ในเวลาพหุนาม สำหรับเซตครอบงำขั้นต่ำจะให้ อัลกอริ ทึมการประมาณค่า α ใน เวลาพหุนาม สำหรับปัญหาการครอบคลุมเซต และในทางกลับกัน ทั้งสองปัญหาเป็นLog-APX-completeจริงๆ^{[ 4 ]}

ความสามารถในการประมาณค่าของการครอบคลุมเซตก็เป็นที่เข้าใจกันดีเช่นกัน: สามารถหาปัจจัยการประมาณค่าลอการิทึมได้โดยใช้อัลกอริทึมโลภแบบง่ายและการหาปัจจัยการประมาณค่าซับลอการิทึมนั้นเป็นปัญหา NP-hard โดยเฉพาะอย่างยิ่ง อัลกอริทึมโลภจะให้การประมาณค่าปัจจัย1 + log| V |ของเซตครอบงำขั้นต่ำ และไม่มีอัลกอริทึมเวลาพหุนามใดที่สามารถบรรลุปัจจัยการประมาณค่าที่ดีกว่าc log| V |สำหรับc > 0 บางค่า เว้นแต่P = NP ^{[ 5 ]}

การลดสองแบบต่อไปนี้แสดงให้เห็นว่าปัญหาชุดครอบงำขั้นต่ำและปัญหาชุดครอบคลุม นั้น เทียบเท่ากันภายใต้การลด L : เมื่อกำหนดอินสแตนซ์ของปัญหาหนึ่งแล้ว เราสามารถสร้างอินสแตนซ์ที่เทียบเท่ากันของปัญหาอื่นได้^{[ 3 ]}

กำหนดกราฟG = ( V , E )โดยที่V = {1, 2, ..., n }จงสร้างอินสแตนซ์ของเซตปกคลุม( U , S )ดังนี้: เอกภพUคือVและตระกูลของเซตย่อยคือS = { S , S , ..., S }โดยที่S ประกอบด้วยจุดยอดv และจุดยอดทั้งหมดที่ อยู่ ติดกับvในG

ถ้าDเป็นเซตครอบคลุมสำหรับGแล้วC = { S  : v ∈ D }จะเป็นคำตอบที่เป็นไปได้ของปัญหาเซตครอบคลุม โดยที่| C | = | D |ในทางกลับกัน ถ้าC = { S  : v ∈ D } เป็นคำ ตอบ ที่เป็นไปได้ของปัญหาเซตครอบคลุม แล้วDจะเป็นเซตครอบคลุมสำหรับGโดยที่| D | = | C |

ดังนั้น ขนาดของเซตครอบงำขั้นต่ำสำหรับGจึงเท่ากับขนาดของเซตปกคลุมขั้นต่ำสำหรับ( U , S )ยิ่งไปกว่านั้น มีอัลกอริทึมง่ายๆ ที่แปลงเซตครอบงำเป็นเซตปกคลุมที่มีขนาดเท่ากันและในทางกลับกัน โดยเฉพาะอย่างยิ่ง อัลกอริ ทึมการประมาณค่า α ที่มีประสิทธิภาพ สำหรับการปกคลุมเซตจะให้ประสิทธิภาพในการประมาณค่า αสำหรับเซตครอบงำขั้นต่ำด้วย

ตัวอย่างเช่น จากกราฟGที่แสดงทางด้านขวา เราสร้างเซตปกคลุม (set cover) ที่มีเอกภพU = {1, 2, ..., 6}และเซตย่อยS = {1, 2, 5}, S = {1, 2, 3, 5}, S = {2, 3, 4, 6}, S = {3, 4}, S = {1, 2, 5, 6}และS = {3, 5, 6}ในตัวอย่างนี้D = {3, 5}เป็นเซตครอบงำ (dominating set) สำหรับG ซึ่งสอดคล้องกับเซตปกคลุมC = { S , S }ตัวอย่างเช่น จุดยอด4 ∈ Vถูกครอบงำโดยจุดยอด3 ∈ Dและสมาชิก4 ∈ Uอยู่ในเซตS ∈ C

ให้( S , U ) เป็นตัวอย่างของปัญหาการครอบคลุมเซต โดย  มีเอกภพUและตระกูลของเซตย่อยS = { Si i ∈ I };เราสมมติว่าUและเซตดัชนีIไม่มีส่วนร่วมกัน สร้างกราฟG = ( V , E )ดังนี้: เซตของจุดยอดคือV = I ∪ Uมีขอบ{ i , j } ∈ Eระหว่างแต่ละคู่i , j ∈ Iและยังมีขอบ{ i , u }สำหรับแต่ละi ∈ Iและu ∈ Si นั่นคือGเป็นกราฟแยกส่วน : Iเป็นกลุ่มคลิกและUเป็นเซต อิสระ

ถ้าC = { Si i ∈ D }เป็นคำตอบที่เป็นไปได้ของปัญหาเซตปกคลุมสำหรับเซตย่อยD ⊆ I บางเซต แล้วDเป็นเซตครอบงำสำหรับG  โดยที่| D | = | C | : ประการแรก สำหรับแต่ละu ∈ Uจะมีi ∈ Dที่u ∈ Si โดยการสร้างuและiอยู่ติดกันในGดังนั้นuจึงถูกครอบงำโดยiประการที่สอง เนื่องจากDต้องไม่ว่างเปล่า แต่ละi ∈ Iจึงอยู่ติดกับจุดยอดใน D

ในทางกลับกัน ให้Dเป็นเซตครอบคลุมสำหรับGจากนั้นเป็นไปได้ที่จะสร้างเซตครอบคลุมอีกเซตหนึ่งXโดยที่| X | ≤ | D |และX ⊆ I : เพียงแค่แทนที่u ∈ D ∩ U แต่ละตัว ด้วยเพื่อนบ้านi ∈ Iของuจากนั้นC = { S  : i ∈ X }เป็นคำตอบที่เป็นไปได้ของปัญหาเซตครอบคลุม โดยที่| C | = | X | ≤ | D |

ภาพประกอบทางด้านขวาแสดงโครงสร้างสำหรับU = { a , b , c , d , e }, I = {1, 2, 3, 4}, S = { a , b , c }, S = { a , b }, S = { b , c , d }และS = { c , d , e }

ในตัวอย่างนี้C = { S , S }คือเซตปกคลุม ซึ่งสอดคล้องกับเซตครอบงำD = {1, 4}

D = { a , 3, 4}เป็นเซตครอบคลุมอีกเซตหนึ่งสำหรับกราฟ Gเมื่อกำหนด D แล้ว เราสามารถสร้างเซตครอบคลุม X = {1, 3, 4}ซึ่งมีขนาดไม่ใหญ่กว่า Dและเป็นเซตย่อยของ Iได้ เซตครอบคลุม Xสอดคล้องกับเซตปกคลุม C = { S , S , S }

ถ้ากราฟมีดีกรีสูงสุด Δ อัลกอริทึมการประมาณแบบโลภจะพบ การประมาณ O (log Δ)ของเซตครอบงำขั้นต่ำ นอกจากนี้ ให้d เป็นจำนวนสมาชิกของเซตครอบงำที่ได้จากการใช้การประมาณแบบโลภ ความสัมพันธ์ต่อไปนี้จะเป็นจริงโดยที่NคือจำนวนโหนดและMคือจำนวนขอบในกราฟแบบไม่มีทิศทางที่กำหนด^{[ 6 ]}สำหรับ Δ คงที่ สิ่งนี้มีคุณสมบัติเป็นเซตครอบงำสำหรับ การเป็นสมาชิก APXในความเป็นจริง มันคือ APX-complete ^{[ 7 ]}${\displaystyle d_{g}\leq N+1-{\sqrt {2M+1}}}$

ปัญหาดังกล่าวยอมรับแผนการประมาณค่าแบบพหุนามเวลา (PTAS) สำหรับกรณีพิเศษ เช่นกราฟดิสก์หน่วยและกราฟระนาบ^{[ 8 ]}สามารถค้นหาเซตครอบงำขั้นต่ำได้ในเวลาเชิงเส้นในกราฟอนุกรม-ขนาน^{[ 9 ]}

เซตครอบงำขั้นต่ำของ กราฟ nจุดยอดสามารถหาได้ในเวลาO (2 ⁿ n )โดยการตรวจสอบเซตย่อยของจุดยอดทั้งหมดFomin, Grandoni & Kratsch (2009)แสดงวิธีการหาเซตครอบงำขั้นต่ำในเวลาO (1.5137 ⁿ )และพื้นที่เลขชี้กำลัง และในเวลาO (1.5264 ⁿ )และพื้นที่พหุนาม อัลกอริทึมที่เร็วกว่า โดยใช้ เวลา O (1.5048 ⁿ )ถูกค้นพบโดยvan Rooij, Nederlof & van Dijk (2009)ซึ่งยังแสดงให้เห็นว่าสามารถคำนวณจำนวนเซตครอบงำขั้นต่ำได้ในเวลานี้ จำนวนเซตครอบงำขั้นต่ำมีค่าสูงสุด1.7159 ⁿและสามารถแสดงรายการเซตดังกล่าวทั้งหมดได้ในเวลา ^O ( 1.7159 ⁿ ) [ ^{10 ]}

การค้นหาเซตครอบงำที่มีขนาดkมีบทบาทสำคัญในทฤษฎีความซับซ้อนแบบพารามิเตอร์ เป็นปัญหาที่รู้จักกันดีที่สุดสำหรับคลาสW[2]และใช้ในการลดรูปหลายครั้งเพื่อแสดงให้เห็นถึงความยากในการแก้ปัญหาอื่นๆ โดยเฉพาะอย่างยิ่ง ปัญหานี้ไม่สามารถจัดการได้ด้วยพารามิเตอร์คงที่ในแง่ที่ว่าไม่มีอัลกอริทึมที่มีเวลาทำงานf ( k ) n ^O(1)สำหรับฟังก์ชันf ใดๆ เว้นแต่ว่าลำดับชั้น W จะยุบตัวลงเป็น FPT=W[2]

ในทางกลับกัน หากกราฟอินพุตเป็นกราฟระนาบ ปัญหายังคงเป็น NP-hard แต่มีอัลกอริทึมแบบพารามิเตอร์คงที่ที่เป็นที่รู้จัก ในความเป็นจริง ปัญหานี้มีเคอร์เนลที่มีขนาดเชิงเส้นใน^{k [} 11 ] ^{และเวลา}การทำงานที่เป็นเลขชี้กำลังใน√ kและลูกบาศก์ในnอาจได้รับโดยการใช้การเขียนโปรแกรมแบบไดนามิกกับการแบ่งสาขาของเคอร์เนล^{[ 12 ]}โดยทั่วไป ปัญหาเซตครอบงำและรูปแบบต่างๆ ของปัญหานี้สามารถแก้ไขได้ด้วยพารามิเตอร์คงที่เมื่อกำหนดพารามิเตอร์โดยทั้งขนาดของเซตครอบงำและขนาดของกราฟย่อยทวิภาคสมบูรณ์ที่ต้องห้าม ที่เล็กที่สุด นั่นคือ ปัญหาเป็น FPT บนกราฟที่ไม่มีไบคลิกซึ่งเป็นคลาสทั่วไปมากของกราฟเบาบางที่รวมถึงกราฟระนาบ^{[ 13 ]}

เซตเสริมของเซตครอบงำ ซึ่งก็คือตัวบล็อกไม่ได้สามารถค้นหาได้ด้วยอัลกอริทึมพารามิเตอร์คงที่บนกราฟใดๆ ก็ได้^{[ 14 ]}

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

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

เซตครอบงำที่เชื่อมต่อกันคือ เซตครอบงำที่เชื่อมต่อกัน ด้วย ถ้าเป็นเซตครอบงำที่เชื่อมต่อกัน เราสามารถสร้างต้นไม้แผ่คลุมของ ได้ โดยที่เป็นเซตของจุดยอดที่ไม่ใช่ใบของต้นไม้ ในทางกลับกัน ถ้าเป็นต้นไม้แผ่คลุมใดๆ ในกราฟที่มีจุดยอดมากกว่าสองจุด จุดยอดที่ไม่ใช่ใบของ จะประกอบกันเป็นเซตครอบงำที่เชื่อมต่อกัน ดังนั้น การหาเซตครอบงำที่เชื่อมต่อกันขั้นต่ำ จึงเทียบเท่ากับการหาต้นไม้แผ่คลุมที่มีจำนวนใบมากที่สุดเท่าที่จะเป็นไปได้ ${\displaystyle S}$${\displaystyle G}$${\displaystyle S}$${\displaystyle T}$${\displaystyle T}$

เซตครอบงำทั้งหมดคือเซตของจุดยอดที่จุดยอดทั้งหมดในกราฟรวมถึงจุดยอดในเซตครอบงำเอง มีจุดยอดข้างเคียงอยู่ในเซตครอบงำ^{[ 17 ]}กล่าวคือ สำหรับทุกจุดยอดจะมีจุดยอดที่ทำให้รูป (c) ด้านบนแสดงเซตครอบงำที่เป็นเซตครอบงำที่เชื่อมต่อกันและเซตครอบงำทั้งหมด ตัวอย่างในรูป (a) และ (b) ไม่ใช่ทั้งสองอย่าง ในทางตรงกันข้ามกับเซตครอบงำแบบง่าย เซตครอบงำทั้งหมดอาจไม่มีอยู่จริง ตัวอย่างเช่น กราฟที่มีจุดยอดหนึ่งจุดหรือมากกว่าและไม่มีขอบ จะไม่มีเซตครอบงำทั้งหมดจำนวนการครอบงำทั้งหมดถูกกำหนดให้เป็นขนาดขั้นต่ำของเซตครอบงำทั้งหมดของGเห็นได้ชัดว่า ${\displaystyle u\in V}$${\displaystyle v\in D}$${\displaystyle \{u,v\}\in E}$${\displaystyle \gamma ^{\text{total}}(G)}$${\displaystyle \gamma ^{\text{total}}(G)\geq \gamma (G)}$

เซตขอบครอบงำ (dominating edge-set ) คือเซตของขอบ (คู่ของจุดยอด) ที่ผลรวมของขอบเหล่านั้นเป็นเซตครอบงำ (dominating set) เซตดังกล่าวอาจไม่มีอยู่จริง (ตัวอย่างเช่น กราฟที่มีจุดยอดหนึ่งจุดขึ้นไปและไม่มีขอบ จะไม่มีเซตดังกล่าว) หากมีอยู่จริง ผลรวมของขอบทั้งหมดในเซตนั้นจะเป็นเซตครอบงำทั้งหมด (total dominating set) ดังนั้น ขนาดที่เล็กที่สุดของเซตขอบครอบงำจึงมีค่าอย่างน้อยที่สุดเท่ากับn ${\displaystyle \gamma ^{\text{total}}(G)/2}$

ในทางตรงกันข้ามเซตที่ครอบงำด้วยขอบคือเซตของขอบทุกเส้นที่ไม่ได้อยู่ในเซตที่ ครอบงำด้วยขอบ จะต้องอยู่ติดกับขอบอย่างน้อยหนึ่งเส้นในเซตที่ครอบงำด้วยขอบนั้น เซตดังกล่าวมีอยู่เสมอ (ตัวอย่างเช่น เซตของขอบทั้งหมดเป็นเซตที่ครอบงำด้วยขอบ) ${\displaystyle D}$${\displaystyle D}$${\displaystyle D}$

เซตk-ครอบงำคือเซตของจุดยอดที่แต่ละจุดยอดที่ไม่ได้อยู่ในเซตนั้นมีเพื่อนบ้านอย่างน้อยkจุดในเซตนั้น (เซตครอบงำมาตรฐานคือเซต 1-ครอบงำ) ในทำนองเดียวกัน เซต k-ทูเพิลครอบงำคือเซตของจุดยอดที่แต่ละจุดยอดในกราฟนั้นมีเพื่อนบ้านอย่างน้อยkจุดในเซตนั้น (เซตครอบงำทั้งหมดคือเซต 1-ทูเพิลครอบงำ) สามารถหา ค่าประมาณ (1 + log n )ของ เซต k- ทูเพิลครอบงำ ขั้นต่ำได้ในเวลาพหุนาม ^{[ 18 ]}ทุกกราฟยอมรับ เซต k-ครอบงำ (ตัวอย่างเช่น เซตของจุดยอดทั้งหมด) แต่มีเพียงกราฟที่มีดีกรีขั้นต่ำk − 1 เท่านั้น ที่ยอมรับ เซต k-ทูเพิลครอบงำ อย่างไรก็ตาม แม้ว่ากราฟจะยอมรับ เซต k- ทูเพิลครอบงำ แต่เซต k-ทูเพิลครอบงำขั้นต่ำ อาจมีขนาดใหญ่เกือบ kเท่าของ เซต k-ครอบงำขั้นต่ำสำหรับกราฟเดียวกัน^{[ 19 ]} การประมาณ ค่า(1.7 + log Δ)ของ เซตที่ครอบงำ k ขั้นต่ำ สามารถพบได้ในเวลาพหุนามเช่นกัน

เซตครอบงำเศษส่วนถูกกำหนดจากฟังก์ชันครอบงำเศษส่วนซึ่งเป็นฟังก์ชันที่สำหรับทุกจุดยอดผลรวมของในบริเวณใกล้เคียงแบบปิดมีค่าอย่างน้อย 1 ^{[ 20 ]}จำนวนการครอบงำเศษส่วนคือน้ำหนักรวมขั้นต่ำ (ผลรวมของค่าจุดยอดทั้งหมด) ของฟังก์ชันดังกล่าว และเป็นไปตามเงื่อนไขสำหรับกราฟปกติ a ที่มีจุดยอด ( ) จำนวนการครอบงำเศษส่วนเท่ากับ ${\displaystyle f:V(G)\to [0,1]}$${\displaystyle v\in V}$${\displaystyle f}$${\displaystyle N[v]}$${\displaystyle \gamma _{f}(G)}$${\displaystyle \gamma _{f}(G)\leq \gamma (G)}$${\displaystyle k}$${\displaystyle n}$${\displaystyle k\geq 1}$${\displaystyle n/(k+1)}$

เซตครอบงำแบบดาว คือเซตย่อย ของโดยที่สำหรับทุกจุดยอดในเซตดาวของ(เซตของขอบที่อยู่ติดกับ) จะตัดกับเซตดาวของจุดยอดบางจุดในอย่างชัดเจน ถ้ามีจุดยอดโดดเดี่ยวก็จะไม่มีเซตครอบงำแบบดาว (เนื่องจากเซตดาวของจุดยอดโดดเดี่ยวว่างเปล่า) ถ้าไม่มีจุดยอดโดดเดี่ยว เซตครอบงำทุกเซตจะเป็นเซตครอบงำแบบดาว และในทางกลับกัน ความแตกต่างระหว่างการครอบงำแบบดาวและการครอบงำแบบปกติจะมีความสำคัญมากขึ้นเมื่อพิจารณารูปแบบเศษส่วน^{[ 21 ]}${\displaystyle D}$${\displaystyle V}$${\displaystyle v}$${\displaystyle V}$${\displaystyle v}$${\displaystyle v}$${\displaystyle D}$${\displaystyle G}$${\displaystyle G}$

การแบ่งกลุ่มแบบโดมาติกคือการแบ่งกลุ่มจุดยอดออกเป็นเซตครอบงำที่ไม่ซ้ำกัน จำนวนโดมาติก คือขนาดสูงสุดของการแบ่งกลุ่มแบบโดมาติก

เซตครอบงำนิรันดร์เป็นรูปแบบไดนามิกของการครอบงำ โดยที่จุดยอดในเซตครอบงำจะถูกเลือกและแทนที่ด้วยจุดยอดข้างเคียง( ที่ไม่อยู่ในเซต ครอบงำ ) โดยที่เซตที่ถูกแก้ไขแล้วก็ยังคงเป็นเซตครอบงำ และกระบวนการนี้สามารถทำซ้ำได้เรื่อยๆ ตลอดลำดับการเลือกจุดยอดที่ไม่มีที่  สิ้นสุด ${\displaystyle v}$${\displaystyle D}$${\displaystyle u}$${\displaystyle u}$${\displaystyle D}$${\displaystyle D}$${\displaystyle v}$

เซตครอบงำที่มีประสิทธิภาพ (เรียกอีกอย่างว่าเซต ed หรือเซตครอบงำที่สมบูรณ์แบบอิสระ^{[ 22 ]} ) คือเซตครอบงำที่มีคุณสมบัติเพิ่มเติมว่าจุดยอดทุกจุดในกราฟจะถูกครอบงำโดย จุดยอด เพียงจุดเดียวในเซต^{[ 23 ]}

เซตการครอบงำแบบโรมันถูกกำหนดผ่านฟังก์ชันการครอบงำแบบโรมันซึ่งกำหนดค่าให้กับแต่ละจุดยอดจากค่าหนึ่งไปยังอีกจุดยอดหนึ่ง โดยที่ทุกจุดยอดที่ได้รับค่า 0 จะอยู่ติดกับจุดยอดที่ได้รับค่า 2 อย่างน้อยหนึ่งจุด จำนวนการครอบงำแบบโรมันคือผลรวมขั้นต่ำของค่าจุดยอดทั้งหมดเหนือฟังก์ชันดังกล่าวทั้งหมด แนวคิดนี้ได้รับแรงบันดาลใจจากกลยุทธ์การป้องกันของจักรวรรดิโรมัน โดยที่จุดยอดแทนเมืองและค่าแทนกองทหารที่ประจำการ สำหรับกราฟใดๆ, , โดยที่ขอบล่างบรรลุได้เฉพาะกราฟว่าง เท่านั้น ^{[ 24 ]}${\displaystyle \{0,1,2\}}$${\displaystyle \gamma _{R}(G)}$${\displaystyle G}$${\displaystyle \gamma (G)\leq \gamma _{R}(G)\leq 2\gamma (G)}$

เซตครอบงำทั่วโลกคือเซตครอบงำของกราฟที่เป็นเซตครอบงำของกราฟส่วนเติม เต็มด้วย จำนวนการครอบงำทั่วโลกคือจำนวนสมาชิกขั้นต่ำของเซตครอบงำทั่วโลก หรือเทียบเท่ากัน เซตครอบงำเป็นเซตครอบงำทั่วโลกก็ต่อเมื่อสำหรับแต่ละจุดยอดจะมีจุดยอดที่ทำให้ไม่ติดกับ ตาม ^คำนิยามและสำหรับกราฟที่มีจุดยอดก็ต่อเมื่อหรือ^{[ 25} ]${\displaystyle G}$${\displaystyle {\overline {G}}}$${\displaystyle \gamma _{g}(G)}$${\displaystyle S}$${\displaystyle v\in V-S}$${\displaystyle u\in S}$${\displaystyle u}$${\displaystyle v}$${\displaystyle \gamma _{g}(G)=\gamma _{g}{\big (}{\overline {G}}{\big )}}$${\displaystyle \gamma (G)\leq \gamma _{g}(G)}$${\displaystyle G}$${\displaystyle p}$${\displaystyle \gamma _{g}(G)=p}$${\displaystyle G=K_{p}}$${\displaystyle G={\overline {K_{p}}}}$

เซตครอบงำที่ได้รับการรับรองคือเซตครอบงำซึ่งทุกจุดยอดในเซตมีเพื่อนบ้านนอกเซตอย่างน้อยศูนย์หรือสองจุด^{[ 26 ]}จำนวนการครอบงำที่ได้รับการรับรอง คือขนาดขั้นต่ำของเซตครอบงำที่ได้รับการรับรอง เห็นได้ชัดว่าและความเท่าเทียมกันเกิดขึ้นเมื่อใดก็ตามที่กราฟไม่มีจุดยอดสนับสนุนที่อ่อนแอ (โดยเฉพาะอย่างยิ่งเมื่อ) สำหรับกราฟที่เชื่อมต่อกัน ${\displaystyle \gamma _{\text{cer}}(G)}$${\displaystyle \gamma _{\text{cer}}(G)\geq \gamma (G)}$${\displaystyle \delta (G)\geq 2}$${\displaystyle \gamma _{\text{cer}}(G)\leq 2\gamma (G)}$

เซตครอบงำคู่ของกราฟคือเซตครอบงำของจุดยอดที่กราฟย่อยเหนี่ยวนำ มี การจับคู่ที่สมบูรณ์แบบอย่างน้อยหนึ่งรายการ[ ^{27 ] จำนวน}การครอบงำคู่คือจำนวนสมาชิกขั้นต่ำของเซตครอบงำคู่ของแนวคิดนี้จำลองสถานการณ์ที่ยามถูกวางไว้ที่จุดยอดของกราฟเพื่อครอบงำ (ปกป้อง) จุดยอดทั้งหมด โดยมีข้อจำกัดเพิ่มเติมว่ายามแต่ละคนจะได้รับยามที่อยู่ติดกันอีกคนหนึ่งเป็นตัวสำรอง ${\displaystyle G=(V,E)}$${\displaystyle S}$${\displaystyle G[S]}$${\displaystyle \gamma _{p}(G)}$${\displaystyle G}$

รูปแบบอื่นๆ ได้แก่

• ชุดครอบงำที่ถูกจำกัด^{[ 28 ]}
• ชุดครอบงำที่ปลอดภัย^{[ 29 ]}
• ชุดครอบงำที่เชื่อมต่อสามเท่า^{[ 30 ]}
• ลงนามชุดครอบงำ^{[ 31 ]}
• ลบชุดที่ครอบงำ^{[ 32 ]}และ
• ชุดที่ครอบงำที่เป็นมิตร^{[ 33 ]}

• ข้อสันนิษฐานของวิซิง (Vizing's conjecture ) – เชื่อมโยงจำนวนการครอบงำของผลคูณคาร์ทีเซียนของกราฟกับจำนวนการครอบงำของตัวประกอบของกราฟนั้น
• ตั้งค่าปัญหาการปกปิด
• หมายเลขพันธนาการ
• ตัวบล็อกที่ไม่ปิดกั้น – ส่วนเสริมของเซ็ตที่ครองเกม
• จุดยอดสากล – เซตครอบงำที่มีจุดยอดเดียว

• Grandoni, F. (2006), "หมายเหตุเกี่ยวกับความซับซ้อนของเซตครอบงำขั้นต่ำ", Journal of Discrete Algorithms , 4 (2): 209– 214, CiteSeerX  10.1.1.108.3223 , doi : 10.1016/j.jda.2005.03.002.
• Guha, S.; Khuller, S. (1998), "อัลกอริทึมการประมาณค่าสำหรับเซตครอบงำที่เชื่อมต่อกัน" (PDF) , Algorithmica , 20 (4): 374– 387, doi : 10.1007/PL00009201 , hdl : 1903/830 , S2CID  1249122.
• เฮนส์, เทเรซา ดับเบิลยู. ; เฮเดตนีมี, สตีเฟน; สเลเตอร์, ปีเตอร์ (1998a), พื้นฐานของการครอบงำในกราฟ , มาร์เซล เดกเกอร์, ISBN 0-8247-0033-3, OCLC  37903553.
• เฮนส์, เทเรซา ดับเบิลยู. ; เฮเดตนีมี, สตีเฟน; สเลเตอร์, ปีเตอร์ (1998b), การครอบงำในกราฟ: หัวข้อขั้นสูง , มาร์เซล เดคเกอร์, ISBN 0-8247-0034-1, OCLC  38201061.
• เวสต์, ดักลาส บี. (2001), บทนำสู่ทฤษฎีกราฟ (ฉบับที่ 2), เพียร์สัน เอ็ดดูเคชั่น.