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

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

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

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

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

กราฟทุกกราฟมีเซตครอบงำอย่างน้อยหนึ่งเซต: ถ้า${\displaystyle D=V=}$ถ้า D คือ เซตของจุดยอดทั้งหมด ตามคำนิยามแล้วDจะเป็นเซตครอบงำ เนื่องจากไม่มีจุดยอดใดที่...${\displaystyle u\in V\setminus D}$ความท้าทายที่น่าสนใจกว่าคือการค้นหาเซตครอบงำขนาดเล็กจำนวนการครอบงำของGถูกกำหนดดังนี้: ${\displaystyle \gamma (G):=\min\{|D|:D{\text{ is a dominating set of }}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 ) เป็นตัวอย่างของปัญหาเซตปกคลุม (set cover problem โดยมีเอกภพ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เป็นกราฟแยกส่วน (split graph ): Iเป็นคลิก (clique)และUเป็นเซตอิสระ (independent set )

ถ้า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 }

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

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

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

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

เซตขอบครอบงำ (Dominating Edge Set ) คือเซตของขอบ (คู่ของจุดยอด) ที่ผลรวมของขอบเหล่านั้นเป็นเซตครอบงำ (Dominating Set) เซตดังกล่าวอาจไม่มีอยู่จริง (ตัวอย่างเช่น กราฟที่มีจุดยอดหนึ่งจุดขึ้นไปและไม่มีขอบ จะไม่มีเซตดังกล่าว) หากมีอยู่จริง ผลรวมของขอบทั้งหมดในเซตนั้นจะเป็นเซตครอบงำทั้งหมด (Total Dominating Set) ดังนั้น ขนาดที่เล็กที่สุดของเซตขอบครอบงำจึงมีค่าอย่างน้อยที่สุดเท่ากับ ...${\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 ขั้นต่ำ สามารถพบได้ในเวลาพหุนามเช่นกัน

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

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

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

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

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

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

เซตครอบงำระดับโลกคือเซตครอบงำของกราฟ${\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}}}}$[ ^{25 ]​}

เซตครอบงำที่ได้รับการรับรองคือเซตครอบงำซึ่งทุกจุดยอดในเซตมีเพื่อนบ้านนอกเซตเป็นศูนย์หรืออย่างน้อยสองจุด^{[ 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)}$.

เซตครอบงำคู่ของกราฟ${\displaystyle G=(V,E)}$เป็นเซตที่ครอบงำ${\displaystyle S}$ของจุดยอดที่ทำให้กราฟย่อยเหนี่ยวนำ${\displaystyle G[S]}$ประกอบด้วย การจับคู่ที่สมบูรณ์แบบอย่างน้อยหนึ่งรายการ^{[ 27 ]}จำนวนการครอบงำแบบจับคู่${\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), เพียร์สัน เอ็ดดูเคชั่น.