ชุดที่ได้รับการรับรองว่าเหนือกว่า

Q: คุณสมบัติและตัวอย่าง

สำหรับกราฟใดๆ จี {\displaystyle G} ของคำสั่ง n {\displaystyle n} : [ 1 ]

ในทฤษฎีกราฟเซตครอบงำที่ได้รับการรับรองของกราฟ คือ เซตครอบงำประเภทหนึ่งซึ่งจุดยอดทุกจุดในเซตมีเพื่อนบ้านนอกเซตอย่างน้อยศูนย์หรือสองจุด แนวคิดนี้ได้รับการแนะนำโดย Dettlaff, Lemańska, Topp, Ziemann และ Żyliński ในปี 2018 ^{[ 1 ]}

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

คำนิยาม

อนุญาต $G=(V,E)$ เป็นกราฟเซตครอบงำ $D\subseteq V$ เรียกว่าเซตครอบงำที่ได้รับการรับรองถ้าสำหรับทุกจุดยอด $v\in D$ จำนวนเพื่อนบ้านของ $v$ ใน $V\setminus D$ มีค่าเป็นศูนย์หรืออย่างน้อยสอง หรืออีกนัยหนึ่งคือไม่มีจุดยอดใน $D$ มีเพื่อนบ้านอยู่ด้านนอกเพียงรายเดียว $D$ [ ¹^]

หมายเลขการครอบงำที่ได้รับการรับรองของ $G$ ซึ่งแสดงด้วย $\gamma _{\text{cer}}(G)$ คือจำนวนสมาชิกขั้นต่ำของเซตครอบงำที่ได้รับการรับรองใน $G$ เซตครอบงำที่ได้รับการรับรองซึ่งมีจำนวนสมาชิกน้อยที่สุดเรียกว่า... $\gamma _{\text{cer}}$ -ชุด . ^{[ 1 ]}^{[ 2 ]}

จุดยอดของ $D$ สามารถจำแนกประเภทได้โดยพิจารณาจากเพื่อนบ้านใน $V\setminus D$ จุดยอดใน $D$ ไม่มีเพื่อนบ้านใน $V\setminus D$ เรียกว่าเงาซึ่งเป็นจุดยอดใน $D$ โดยมีเพื่อนบ้านเพียงคนเดียวใน $V\setminus D$ เรียกว่าเงาครึ่งหนึ่งและจุดยอดใน $D$ โดยมีเพื่อนบ้านอย่างน้อยสองคนใน $V\setminus D$ เรียกว่าส่องสว่างเซตที่ครอบคลุมจะได้รับการรับรองก็ต่อเมื่อไม่มีจุดยอดที่มีเงาครึ่งหนึ่ง^{[ 1 ]}

คุณสมบัติและตัวอย่าง

สำหรับกราฟใดๆ $G$ ของคำสั่ง $n$ : ^{[ 1 ]}

เซตจุดยอด $V$ เป็นชุดที่ได้รับการรับรองว่าเหนือกว่าเสมอ ดังนั้น $1\leq \gamma _{\text{cer}}(G)\leq n$ .
$\gamma _{\text{cer}}(G)\neq n-1$ สำหรับกราฟใดๆ ก็ตาม
จุดรองรับทุก จุด ของ $G$ เป็นของกลุ่มคนที่ได้รับการรับรองว่ามีอำนาจเหนือกว่าทุกคน
$\gamma _{\text{cer}}(G)=1$ ก็ต่อเมื่อ $G$ มีลำดับอย่างน้อยสามและมีจุดยอดสากล
ถ้า $G_{1},G_{2},\ldots ,G_{k}$ คือส่วนประกอบที่เชื่อมต่อกันของ $G$ , แล้ว $\gamma _{\text{cer}}(G)=\sum _{i=1}^{k}\gamma _{\text{cer}}(G_{i})$ .

จำนวนการครอบงำที่ได้รับการรับรองเป็นที่ทราบแน่ชัดสำหรับตระกูลกราฟหลายตระกูล: ^{[ 1 ]}

สำหรับเส้นทาง $P_{n}$ $P_{n}$ :
- $\gamma _{\text{cer}}(P_{n})=1$ ถ้า $n=1$ หรือ $n=3$
- $\gamma _{\text{cer}}(P_{n})=2$ ถ้า $n=2$
- $\gamma _{\text{cer}}(P_{n})=4$ ถ้า $n=4$
- $\gamma _{\text{cer}}(P_{n})=\lceil n/3\rceil$ มิฉะนั้น
สำหรับรอบ $C_{n}$ $C_{n}$ กับ $n\geq 3$ $n\geq 3$ :
- $\gamma _{\text{cer}}(C_{n})=\lceil n/3\rceil$
สำหรับกราฟฉบับสมบูรณ์ $K_{n}$ $K_{n}$ :
- $\gamma _{\text{cer}}(K_{n})=1$ ถ้า $n=1$ หรือ $n\geq 3$
- $\gamma _{\text{cer}}(K_{n})=2$ ถ้า $n=2$
สำหรับกราฟสองส่วนสมบูรณ์ $K_{m,n}$ $K_{m,n}$ กับ $1\leq m\leq n$ $1\leq m\leq n$ :
- $\gamma _{\text{cer}}(K_{m,n})=1$ ถ้า $m=1$ และ $n>1$
- $\gamma _{\text{cer}}(K_{m,n})=2$ มิฉะนั้น
สำหรับกราฟวงล้อ $W_{n}$ $W_{n}$ :
- $\gamma _{\text{cer}}(W_{n})=1$

ขอบเขตและความสัมพันธ์กับจำนวนการครอบงำ

เนื่องจากเซ็ตที่ได้รับการรับรองว่าเป็นเซ็ตที่เหนือกว่าทุกเซ็ต ล้วนเป็นเซ็ตที่เหนือกว่าทั้งสิ้น $\gamma (G)\leq \gamma _{\text{cer}}(G)$ สำหรับกราฟทั้งหมด $G$ สำหรับกราฟที่เชื่อมต่อกัน $G$ หมายเลขการครอบงำที่ได้รับการรับรองเป็นไปตามเงื่อนไข: ^{[ 1 ]}

\gamma _{\text{cer}}(G)\leq \gamma (G)+|S_{1}(G)|

ที่ไหน $\gamma (G)$ คือเลขแห่งการครอบงำและ $S_{1}(G)$ คือเซตของจุดยอดสนับสนุนที่อ่อนแอ (จุดยอดสนับสนุนที่อยู่ติดกับใบเพียงหนึ่งใบ เท่านั้น ) ขอบเขตนี้มีความแม่นยำ เนื่องจากความเท่าเทียมกันนี้ใช้ได้กับโคโรนาของกราฟใดๆ ที่ไม่มีจุดยอดโดดเดี่ยว ผลที่ตามมาคือ $\gamma _{\text{cer}}(G)\leq 2\gamma (G)$ นอกจากนี้ หากจุดยอดสนับสนุนที่แข็งแกร่งของ $G$ อยู่ติดกับ $k$ จำนวนใบทั้งหมด จากนั้น $\gamma _{\text{cer}}(G)\leq n-k$ [ ¹^]

ความเท่าเทียมกัน $\gamma _{\text{cer}}(G)=\gamma (G)$ ใช้ได้ในหลายกรณี: ^{[ 1 ]}^{[ 2 ]}

ถ้า $G$ ไม่มีจุดรองรับที่อ่อนแอ (โดยเฉพาะอย่างยิ่ง ถ้า $\delta (G)\geq 2$ ), แล้ว $\gamma _{\text{cer}}(G)=\gamma (G)$ .
ถ้า $G$ มีเซตครอบงำขั้นต่ำที่ไม่ซ้ำกัน จากนั้น $\gamma _{\text{cer}}(G)=\gamma (G)$ .
ถ้า $\gamma (G-v)\geq \gamma (G)$ สำหรับทุกจุดยอด $v$ เป็นของอย่างน้อยหนึ่ง $\gamma$ -ชุดของ $G$ , แล้ว $\gamma _{\text{cer}}(G)=\gamma (G)$ .
ถ้า $G$ เป็นการเชื่อมต่อ $P_{4}$ -กราฟฟรีและ $G\neq K_{2}$ , แล้ว $\gamma _{\text{cer}}(G)=\gamma (G)$ .

โดยทั่วไปแล้ว สำหรับกราฟที่เชื่อมต่อกัน $G$ มีลำดับอย่างน้อยสาม $\gamma _{\text{cer}}(G)=\gamma (G)$ ก็ต่อเมื่อ $G$ มี $\gamma$ -ชุด $D$ โดยที่ทุกจุดยอดใน $D$ มีเพื่อนบ้านอย่างน้อยสองคนใน $V\setminus D$ [ ²^]

กราฟ $G$ เรียกว่า $\gamma \gamma _{\text{cer}}$ -สมบูรณ์แบบถ้า $\gamma (H)=\gamma _{\text{cer}}(H)$ สำหรับกราฟย่อยที่เชื่อมต่อกันทุกกราฟ $H\neq K_{2}$ ของ $G$ กราฟคือ $\gamma \gamma _{\text{cer}}$ -สมบูรณ์แบบก็ต่อเมื่อเป็นเช่นนั้น $P_{4}$ -ฟรี^{[ 2 ]}

กราฟที่มีตัวเลขการครอบงำที่ได้รับการรับรองจำนวนมาก

กราฟ $G$ ของคำสั่ง $n$ พอใจ $\gamma _{\text{cer}}(G)=n$ ก็ต่อเมื่อ $G$ เป็นส่วนเติมเต็มของกราฟสมบูรณ์วงโคโรนาของกราฟ หรือการรวมกันแบบไม่ทับซ้อนกันของทั้งสอง^{[ 1 ]}

กราฟมงกุฎคือกราฟที่ได้มาจากโคโรนา $H\circ K_{1}$ โดยการเพิ่มจุดยอดใหม่และเชื่อมต่อเข้ากับจุดยอดรองรับจุดหนึ่งของ $H\circ K_{1}$ กราฟ $G$ ของคำสั่ง $n\geq 3$ พอใจ $\gamma _{\text{cer}}(G)=n-2$ ก็ต่อเมื่อ $G$ เป็น $C_{3}$ , $C_{4}$ หรือกราฟมงกุฎ อาจรวมกับโคโรนาของกราฟและจุดยอดที่แยกเดี่ยว^{[ 1 ]}

ผลกระทบของการปรับเปลี่ยนกราฟ

การเพิ่มเส้นเชื่อมลงในกราฟที่เชื่อมต่อกันไม่สามารถเพิ่มจำนวนการครอบงำที่ได้รับการรับรองได้: $\gamma _{\text{cer}}(G+e)\leq \gamma _{\text{cer}}(G)$ อย่างไรก็ตาม การลบขอบออกจากกราฟและการเพิ่มขอบให้กับกราฟที่ไม่เชื่อมต่อกันอาจทำให้จำนวนการครอบงำที่ได้รับการรับรองเพิ่มขึ้นอย่างไม่แน่นอน^{[ 1 ]}

การเพิ่มจุดยอดใบอาจทำให้จำนวนการครอบงำที่ได้รับการรับรองเพิ่มขึ้นอย่างไม่แน่นอน แต่การเพิ่มจุดยอดที่ไม่ใช่ใบจะทำให้จำนวนการครอบงำที่ได้รับการรับรองเพิ่มขึ้น $v$ ไปยังกราฟ $G$ พอใจ $\gamma _{\text{cer}}(G+v)\leq \gamma _{\text{cer}}(G)+1$ [ ¹^]

อสมการประเภท Nordhaus–Gaddum

สำหรับกราฟ $G$ ของคำสั่ง $n\geq 5$ พร้อมส่วนเสริม ${\overline {G}}$ : ^{[ 1 ]}

\gamma _{\text{cer}}(G)+\gamma _{\text{cer}}({\overline {G}})\leq n+2

\gamma _{\text{cer}}(G)\cdot \gamma _{\text{cer}}({\overline {G}})\leq 2n

ความเท่าเทียมกันเกิดขึ้นในอสมการทั้งสองพร้อมกันก็ต่อเมื่อ $G$ หรือ ${\overline {G}}$ คือโคโรนาของกราฟบางกราฟ^{[ 1 ]}

ถ้า $\min\{\delta (G),\delta ({\overline {G}})\}\geq 2$ ขอบเขตที่แข็งแกร่งกว่าจะคงอยู่: ^{[ 1 ]}

\gamma _{\text{cer}}(G)+\gamma _{\text{cer}}({\overline {G}})\leq \left\lfloor {\frac {n}{2}}\right\rfloor +2

\gamma _{\text{cer}}(G)\cdot \gamma _{\text{cer}}({\overline {G}})\leq n

ความซับซ้อนในการคำนวณ

ปัญหาการหาจำนวนการครอบงำที่ได้รับการรับรองนั้นเป็นปัญหาNP-hardแม้แต่สำหรับ กราฟย่อยลูกบาศก์ ระนาบ สองส่วนที่ ไม่มีใบ ซึ่งเป็นผลมาจากความเท่าเทียมกัน $\gamma _{\text{cer}}(G)=\gamma (G)$ สำหรับกราฟที่ไม่มีจุดรองรับที่อ่อนแอและความยาก NP ที่ทราบของปัญหาการครอบงำในคลาสกราฟดังกล่าว^{[ 1 ]}

การพิจารณาว่า $\gamma (G)\neq \gamma _{\text{cer}}(G)$ สำหรับกราฟที่กำหนด $G$ ยังเป็นปัญหา NP-hard ด้วย แม้กระทั่งเมื่อ $G$ ^{มีจุด รองรับ}ที่อ่อนแอเพียงจุดเดียว ซึ่งแสดงให้เห็นได้จากการลดรูปจาก3SAT [ ³^]

ดูเพิ่มเติม

[ 1 ]

[ 2 ]

มีจุด รองรับ