ในทฤษฎีกราฟเซตครอบงำทั่วโลกคือเซตครอบงำ${\displaystyle S}$ของกราฟ${\displaystyle G}$นั่นคือเซตครอบงำของกราฟส่วนเติมเต็ม ด้วยเช่นกัน${\displaystyle {\bar {G}}}$ตัวเลขการครอบงำระดับโลก${\displaystyle \gamma _{g}(G)}$คือจำนวนสมาชิกขั้นต่ำของเซตครอบงำทั่วโลกของ${\displaystyle G}$แนวคิดนี้ได้รับการนำเสนอโดย E. Sampathkumar ในปี 1989 ^{[ 1 ]}

อนุญาต${\displaystyle G=(V,E)}$เป็นกราฟที่มีเซตของจุดยอด${\displaystyle V}$และชุดขอบ${\displaystyle E}$ชุดหนึ่ง${\displaystyle S\subseteq V}$เป็น ชุด ที่ครอบงำ${\displaystyle G}$ถ้าทุกจุดยอดใน${\displaystyle VS}$อยู่ติดกับจุดยอดอย่างน้อยหนึ่งจุดใน${\displaystyle S}$ชุดที่โดดเด่น${\displaystyle S}$เรียกว่าเซตครอบงำทั่วโลก (หรือเซต gd ) ถ้า${\displaystyle S}$นอกจากนี้ยังเป็นเซตที่ครอบงำของส่วนเติมเต็มอีกด้วย${\displaystyle {\bar {G}}}$[ ^{1 ]​}

ในทำนองเดียวกัน ชุดที่ครอบงำ${\displaystyle S}$ของ${\displaystyle G}$เซตนี้จะเป็นเซตครอบงำทั่วโลกก็ต่อเมื่อสำหรับแต่ละจุดยอด${\displaystyle v\in VS}$มีจุดยอดอยู่จุดหนึ่ง${\displaystyle u\in S}$โดยที่${\displaystyle u}$ไม่ได้อยู่ติดกับ${\displaystyle v}$ใน${\displaystyle G}$[ ^{1 ]​}

คุณสมบัติต่อไปนี้ใช้ได้กับกราฟทุกประเภท${\displaystyle G}$: ^{[ 1 ]}

• ${\displaystyle \gamma _{g}(G)=\gamma _{g}({\bar {G}})}$
• ${\displaystyle \gamma (G)\leq \gamma _{g}(G)}$, ที่ไหน${\displaystyle \gamma (G)}$คือจำนวนการครอบงำของ${\displaystyle G}$
• ${\displaystyle {\bar {\gamma }}(G)\leq \gamma _{g}(G)}$, ที่ไหน${\displaystyle {\bar {\gamma }}(G)=\gamma ({\bar {G}})}$
• ${\displaystyle {\frac {\gamma (G)+{\bar {\gamma }}(G)}{2}}\leq \gamma _{g}(G)\leq \gamma (G)+{\bar {\gamma }}(G)}$

สำหรับกราฟ${\displaystyle G}$ของคำสั่ง${\displaystyle p}$โดยไม่มีจุดยอดที่แยกเดี่ยว: ^{[ 1 ]}

• ${\displaystyle \gamma (G)+\gamma _{g}(G)\leq p+1}$
• ${\displaystyle \gamma _{g}(G)\leq \max\{\chi (G),\chi ({\bar {G}})\}}$, ที่ไหน${\displaystyle \chi (G)}$คือจำนวนโครมาติกของ${\displaystyle G}$

จำนวนการครอบงำทั่วโลกแสดงให้เห็นถึงความไม่เปลี่ยนแปลงภายใต้การดำเนินการกราฟ บางอย่าง ตัวอย่างเช่น สำหรับวัฏจักร${\displaystyle C_{n}}$(กับ${\displaystyle n\neq 3,n\neq 5}$) จำนวนการครอบงำทั่วโลกยังคงไม่เปลี่ยนแปลงภายใต้การดำเนินการทำซ้ำขอบ และเช่นเดียวกันสำหรับล้อ${\displaystyle W_{n}}$[ ^{2 ]​}

สำหรับตระกูลกราฟเฉพาะ ได้มีการกำหนดจำนวนการครอบงำทั่วโลกไว้แล้ว: ^{[ 1 ] [ 2 ]}

• สำหรับกราฟที่สมบูรณ์${\displaystyle K_{p}}$หรือส่วนเติมเต็มของมัน${\displaystyle {\bar {K}__{p}}$:${\displaystyle \gamma _{g}(G)=p}$
• สำหรับกราฟสองส่วนที่สมบูรณ์${\displaystyle K_{m,n}}$กับ${\displaystyle 2\leq m\leq n}$:${\displaystyle \gamma _{g}(K_{m,n})=n}$
• สำหรับรอบ หนึ่ง${\displaystyle C_{n}}$กับ${\displaystyle n\neq 3}$และ${\displaystyle n\neq 5}$:${\displaystyle \gamma _{g}(C_{n})=\lceil n/3\rceil }$
• สำหรับเส้นทาง${\displaystyle P_{n}}$กับ${\displaystyle n\geq 4}$:${\displaystyle \gamma _{g}(P_{n})=\lceil n/3\rceil }$
• สำหรับล้อ${\displaystyle W_{n}}$:${\displaystyle \gamma _{g}(W_{n})=4}$ถ้า${\displaystyle n=4}$, และ${\displaystyle \gamma _{g}(W_{n})=3}$มิฉะนั้น

หมายเลขโดมาติกทั่วโลก${\displaystyle d_{g}(G)}$คือลำดับสูงสุดของการแบ่งกลุ่มเซตของจุดยอด${\displaystyle V}$เข้าสู่เซตครอบงำระดับโลก ในทำนองเดียวกับความสัมพันธ์ระหว่างจำนวนการครอบงำและจำนวนโดมาติกเราจึงมี${\displaystyle d_{g}(G)=d_{g}({\bar {G}})}$และ${\displaystyle d_{g}(G)\leq d(G)\leq \delta (G)+1}$, ที่ไหน${\displaystyle d(G)}$คือหมายเลขโดเมนและ${\displaystyle \delta (G)}$คือระดับขั้นต่ำของ${\displaystyle G}$[ ^{1 ]​}

ปัญหาของการค้นหาเซตครอบงำทั่วโลกขั้นต่ำเป็นปัญหาNP-hardซึ่งได้รับการพิสูจน์โดย Brigham และ Dutton (1990) ผ่านการลดรูปจากปัญหาเซตครอบงำซึ่งเป็นที่ทราบกันดีว่าเป็นปัญหา NP-hard ^{[ 3 ] [ 4 ]}

ปัญหายังคงเป็น NP-hard แม้สำหรับคลาสกราฟที่จำกัด รวมถึงกราฟระนาบและกราฟแยกสำหรับกราฟแยก เซตครอบงำทั่วโลกใดๆ จะถูกสร้างขึ้นโดยเซตครอบงำของกราฟหรือโดยเซตครอบงำที่เสริมด้วยจุดยอดจากเซตอิสระ^{[ 3 ]}

ได้มีการพัฒนาอัลกอริทึมทั้งแบบแม่นยำและแบบฮิวริสติกสำหรับปัญหาการครอบงำทั่วโลก: ^{[ 3 ]}

อัลกอริทึมที่แม่นยำ:

• การกำหนดสูตร การเขียนโปรแกรมเชิงเส้นจำนวนเต็ม ( ILP) โดยใช้${\displaystyle 2n}$ข้อจำกัดเพื่อให้มั่นใจถึงการครอบงำในทั้งสองด้าน${\displaystyle G}$และ${\displaystyle {\bar {G}}}$
• อัลกอริทึมการแจงนับโดยปริยายที่ใช้การค้นหาแบบไบนารีเหนือขนาดของคำตอบที่เป็นไปได้ โดยมีขอบเขตล่างและขอบเขตบนเป็นแนวทาง

อัลกอริทึมแบบฮิวริสติก:

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

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

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

• แฮร์ริส, เอลิซาเบธ มารี (สิงหาคม 2012). กราฟเสถียรการครอบงำระดับโลก (ปริญญาโท). มหาวิทยาลัยรัฐอีสต์เทนเนสซี.