ชุดครอบงำอิสระ

ในทฤษฎีกราฟเซตครอบงำอิสระสำหรับกราฟเป็นเซตย่อยซึ่งเป็นทั้งเซตครอบงำและเซตอิสระหรือกล่าวอีกนัยหนึ่งคือเป็น เซต อิสระสูงสุด[ 1 ]
จำนวนการครอบงำอิสระของกราฟคือขนาดของเซตครอบงำอิสระที่เล็กที่สุด (เทียบเท่ากับเซตอิสระสูงสุดที่เล็กที่สุด) [ 1 ]สัญลักษณ์ได้รับการแนะนำโดย Cockayne และ Hedetniemi [ 2 ] [ 3 ]
ประวัติศาสตร์
แนวคิดของเซตครอบงำอิสระเกิดขึ้นจากปัญหาหมากรุกในปี พ.ศ. 2405 เดอ จาเอนิช ได้ตั้งปัญหาในการหาจำนวนควีน ที่ไม่โจมตีกันน้อยที่สุด ที่สามารถวางบนกระดานหมากรุกได้ เพื่อให้ทุกช่องถูกโจมตีโดยควีนอย่างน้อยหนึ่งตัว[ 4 ]การจำลองกระดานหมากรุกเป็นกราฟของควีนค่าต่ำสุดนี้คือจำนวนการครอบงำที่เป็นอิสระสำหรับแผนผังควีนมาตรฐานขนาด 8x8 นั้น,, และ[ 1 ]
ทฤษฎีการครอบงำแบบอิสระได้รับการกำหนดอย่างเป็นทางการโดยBergeและOreในปี พ.ศ. 2505 [ 5 ] [ 6 ] Berge สังเกตว่าเซตอิสระจะเป็นเซตอิสระสูงสุดก็ต่อเมื่อเป็นเซตครอบงำ และเซตอิสระสูงสุดทุกเซตจะเป็นเซตครอบงำขั้นต่ำ[ 5 ]
ขอบเขต
ขอบเขตทั่วไป
เบอร์เกได้กำหนดขอบเขตพื้นฐานในแง่ของลำดับและระดับ สูงสุดของกราฟ: [ 7 ]
สำหรับกราฟที่ไม่มีจุดยอดโดดเดี่ยว: [ 8 ]
และขอบเขตนี้มีความแม่นยำ สำหรับกราฟที่มีดีกรีต่ำสุดอย่างน้อย: [ 9 ]
ยืนยันสมมติฐานก่อนหน้านี้ของฟาวารอน[ 8 ]
ตระกูลกราฟ
สำหรับกราฟที่ไม่มีกรงเล็บ : [ 10 ]
โดยทั่วไปแล้ว สำหรับกราฟ แบบ -free ( star -free) ที่: [ 11 ]
สำหรับกราฟสองส่วน ใดๆ ที่ไม่มีจุดยอดโดดเดี่ยวบนจุดยอด: [ 1 ]
สำหรับต้นไม้ถ้าต้นไม้มีจุดยอดและใบ: [ 12 ]
ถ้าเป็น- กราฟปกติบนจุดยอดที่ไม่มีจุดยอดโดดเดี่ยว จากนั้น: [ 13 ]
สำหรับกราฟลูกบาศก์ที่เชื่อมต่อกัน อื่นๆ นอกเหนือจาก: [ 14 ]
มีการคาดการณ์ว่าขอบเขตดังกล่าวสามารถปรับปรุงให้ดีขึ้นได้สำหรับกราฟลูกบาศก์ที่เชื่อมต่อทั้งหมดที่มีลำดับมากกว่า 10 [ 1 ]
เกี่ยวกับอัตราส่วนระหว่างการครอบงำและการครอบงำอิสระในกราฟลูกบาศก์ที่เชื่อมต่อกัน นอกเหนือจากนั้น: [ 15 ]
สำหรับกราฟระนาบ ใดๆ บนจุดยอด: [ 16 ]
สำหรับกราฟระนาบที่มีเส้นผ่านศูนย์กลาง 2 ขอบเขตสามารถปรับปรุงได้: [ 16 ]
ความสัมพันธ์กับกราฟเส้นและการครอบงำของขอบ
สำหรับกราฟใดๆกราฟเส้นของมันไม่มีกรงเล็บ ดังนั้นจึงเป็นเซตอิสระขั้นต่ำสุดสูงสุดในนอกจากนี้ยังเป็นเซตครอบงำขั้นต่ำในชุดอิสระในสอดคล้องกับการจับคู่ในและชุดที่โดดเด่นในสอดคล้องกับเซตที่ครอบงำขอบในดังนั้นการจับคู่สูงสุดขั้นต่ำ จึง มีขนาดเท่ากับเซตที่ครอบคลุมขอบขั้นต่ำ
ความสัมพันธ์กับพารามิเตอร์การครอบงำอื่นๆ
เนื่องจากการหาค่าต่ำสุดนั้นพิจารณาจากเซตจำนวนน้อยกว่า (โดยพิจารณาเฉพาะเซตครอบงำที่เป็นอิสระเท่านั้น)สำหรับกราฟทั้งหมดในทำนองเดียวกัน เนื่องจากเซตอิสระสูงสุดทุกเซตเป็นเซตอิสระ, ที่ไหนคือจำนวนความเป็นอิสระยิ่งไปกว่านั้น เนื่องจากเซตอิสระสูงสุดทุกเซตเป็นเซตครอบงำขั้นต่ำ, ที่ไหนคือจำนวนการครอบงำสูงสุด (ขนาดสูงสุดของเซตการครอบงำขั้นต่ำ) ซึ่งจะทำให้เกิดห่วงโซ่การครอบงำ : [ 17 ]
ความไม่เท่าเทียมกันอาจเป็นแบบเข้มงวด มีกราฟอยู่ด้วยซึ่งตัวอย่างเช่น สมมติว่าเป็นกราฟดาวคู่ที่ประกอบด้วยจุดยอด, ที่ไหนขอบของแต่ละคำนิยามไว้ดังนี้:อยู่ติดกับ,อยู่ติดกับ, และอยู่ติดกับแต่ละ. แล้วเนื่องจากเป็นเซตครอบงำที่เล็กที่สุด ถ้า, แล้วเนื่องจากเป็นเซตครอบงำที่เล็กที่สุดที่เป็นอิสระด้วย (เป็นเซตอิสระสูงสุดที่เล็กที่สุด)
อย่างไรก็ตาม ขอบเขตมีความคมชัดพร้อมกันสำหรับโคโรนาของกราฟใดๆซึ่งเป็นที่น่าพอใจ[ 1 ]
Cockayne และ Mynhardt ได้ระบุลำดับของค่าที่เป็นไปได้ไว้ดังนี้: [ 18 ]ลำดับของจำนวนเต็มสามารถเกิดขึ้นได้ดังนี้สำหรับกราฟบางส่วนก็ต่อเมื่อ,หมายความว่า, และหมายความว่า.
ความซับซ้อนในการคำนวณ
การพิจารณาว่าสำหรับกราฟที่กำหนดและจำนวนเต็มโดยทั่วไปแล้ว P เป็นปัญหา NP-complete [ 19 ]และยังคงเป็น NP-complete แม้ว่าจะจำกัดเฉพาะกราฟสองส่วนกราฟเส้นกราฟวงกลมกราฟดิสก์หน่วยหรือกราฟลูกบาศก์ระนาบ[ 1 ] ยิ่งไปกว่านั้น Irving แสดงให้เห็นว่าไม่มีอัลกอริทึมเวลาพหุนามใดที่จะประมาณจำนวนการครอบงำอิสระภายในปัจจัยคงที่ได้ เว้นแต่ว่าP = NP [ 20 ]
ในทางกลับกัน จำนวนการครอบงำอิสระสามารถคำนวณได้ในเวลาเชิงเส้นสำหรับต้นไม้[ 21 ]และในเวลาพหุนามสำหรับกราฟคอร์ดัล[ 22 ]และกราฟโคคอมแพริบิลิตี้[ 23 ]
กราฟที่สมบูรณ์แบบในการครอบงำ
กราฟเรียกว่ากราฟที่สมบูรณ์แบบการครอบงำ (domination-perfect graph)ถ้าในทุกซับกราฟที่เหนี่ยวนำของ[ 24 ]เนื่องจากกราฟย่อยที่เหนี่ยวนำของกราฟที่ไม่มีกรงเล็บเป็นกราฟที่ไม่มีกรงเล็บ ดังนั้นกราฟที่ไม่มีกรงเล็บทุกกราฟจึงเป็นกราฟที่สมบูรณ์แบบในการครอบงำด้วย[ 25 ]
จากผลการศึกษาของซัมเนอร์และมัวร์ กราฟจะเป็นกราฟสมบูรณ์แบบเชิงการครอบงำก็ต่อเมื่อสำหรับกราฟย่อยเหนี่ยวนำทุกกราฟกับ[ 24 ] Zverovich และ Zverovich ได้ให้ลักษณะเฉพาะที่สมบูรณ์: กราฟจะสมบูรณ์แบบการครอบงำก็ต่อเมื่อไม่มีกราฟเฉพาะ 17 กราฟใดเป็นกราฟย่อยที่เหนี่ยวนำ[ 26 ]
กราฟที่ครอบคลุมดี
กราฟจะครอบคลุมพื้นที่ได้ดีหากนั่นคือ เซตอิสระสูงสุดทุกเซตเป็นเซตอิสระสูงสุด แนวคิดนี้ได้รับการแนะนำโดย Plummer [ 27 ] Ravindra ได้กำหนดลักษณะของกราฟสองส่วนที่ครอบคลุมอย่างดี: กราฟสองส่วนที่เชื่อมต่อกันจะถูกครอบคลุมอย่างดีก็ต่อเมื่อมีการจับคู่ที่สมบูรณ์แบบโดยที่สำหรับทุกขอบกราฟย่อยที่เกิดจากเป็นกราฟสองส่วนที่สมบูรณ์[ 28 ]ผลที่ตามมาคือ ต้นไม้จะได้รับการครอบคลุมอย่างดีก็ต่อเมื่อเป็นเช่นนั้นหรือโคโรนาของต้นไม้[ 1 ]