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

ตัวเลขแสดงการครอบครองของโรมันในกราฟนั้น วัดจำนวนกองทหารโรมันขั้นต่ำทั้งหมดที่จำเป็นในการปกป้องเมืองทั้งหมดตามกลยุทธ์นี้

อนุญาต${\displaystyle G=(V,E)}$เป็นกราฟฟังก์ชันครอบงำแบบโรมัน (RDF) คือฟังก์ชันหนึ่ง${\displaystyle f:V\to \{0,1,2\}}$โดยที่สำหรับทุกจุดยอด${\displaystyle v}$กับ${\displaystyle f(v)=0}$มีจุดยอดอยู่จุดหนึ่ง${\displaystyle u}$ติดกับ${\displaystyle v}$กับ${\displaystyle f(u)=2}$[ ^{1 ]​}

น้ำหนักของฟังก์ชันการครอบงำแบบโรมัน${\displaystyle f}$เป็น${\displaystyle w(f)=\sum _{v\in V}f(v)}$เลขการปกครองของโรมัน${\displaystyle \gamma _{R}(G)}$เป็นน้ำหนักขั้นต่ำในบรรดาฟังก์ชันครอบงำโรมันทั้งหมดสำหรับ${\displaystyle G}$.

ในทำนองเดียวกัน ให้${\displaystyle (V_{0},V_{1},V_{2})}$เป็นพาร์ติชันเรียงลำดับของ${\displaystyle V}$ที่ไหน${\displaystyle V_{i}=\{v\in V:f(v)=i\}}$. แล้ว${\displaystyle f}$ฟังก์ชันนี้เรียกว่าฟังก์ชันครอบงำแบบโรมันก็ต่อเมื่อทุกจุดยอดใน${\displaystyle V_{0}}$อยู่ติดกับจุดยอดอย่างน้อยหนึ่งจุดใน${\displaystyle V_{2}}$[ ^{1 ]​}

สำหรับกราฟฉบับสมบูรณ์${\displaystyle K_{n}}$กับ${\displaystyle n\geq 2}$,${\displaystyle \gamma _{R}(K_{n})=2}$ซึ่งทำได้โดยการกำหนดค่า 2 ให้กับจุดยอดใดจุดหนึ่ง และค่า 0 ให้กับจุดยอดอื่นๆ ทั้งหมด

สำหรับกราฟเส้นทาง${\displaystyle P_{n}}$และกราฟวงจร${\displaystyle C_{n}}$,${\displaystyle \gamma _{R}(P_{n})=\gamma _{R}(C_{n})=\lceil 2n/3\rceil }$[ ^{1 ]​}

สำหรับกราฟว่างเปล่า${\displaystyle {\overline {K}}_{n}}$,${\displaystyle \gamma _{R}({\overline {K}}_{n})=n}$เนื่องจากแต่ละจุดยอดจะต้องได้รับการกำหนดค่าอย่างน้อย 1 ค่า

สำหรับ กราฟ n -partite ที่สมบูรณ์${\displaystyle K_{m_{1},m_{2},\dots ,m_{n}}}$ด้วยขนาดพาร์ติชั่น${\displaystyle m_{1}\leq m_{2}\leq \dots \leq m_{n}}$: ^{[ 1 ]}

• ${\displaystyle \gamma _{R}(K_{m_{1},\dots ,m_{n}})=2}$ถ้า${\displaystyle m_{1}=1}$.
• ${\displaystyle \gamma _{R}(K_{m_{1},\dots ,m_{n}})=3}$ถ้า${\displaystyle m_{1}=2}$.
• ${\displaystyle \gamma _{R}(K_{m_{1},\dots ,m_{n}})=4}$ถ้า${\displaystyle m_{1}\geq 3}$.

Cockayne และคณะได้กำหนดคุณสมบัติหลายประการของการปกครองของโรมันไว้ดังนี้: ^{[ 1 ]}

• สำหรับกราฟใดๆ${\displaystyle G}$,${\displaystyle \gamma (G)\leq \gamma _{R}(G)\leq 2\gamma (G)}$, ที่ไหน${\displaystyle \gamma (G)}$คือเลขแห่งการครอบงำ
• ${\displaystyle \gamma (G)=\gamma _{R}(G)}$ก็ต่อเมื่อ${\displaystyle G}$เป็นกราฟว่างเปล่า
• ถ้า${\displaystyle G}$มีจุดยอดที่มีดีกรี${\displaystyle n-1}$, แล้ว${\displaystyle \gamma _{R}(G)=2}$.
• สำหรับฟังก์ชันการครอบงำแบบโรมันใดๆ${\displaystyle f=(V_{0},V_{1},V_{2})}$:
  • กราฟย่อยที่เกิดจาก${\displaystyle V_{1}}$มีระดับสูงสุดไม่เกิน 1
  • ไม่มีรอยต่อขอบ${\displaystyle V_{1}}$และ${\displaystyle V_{2}}$.
  • จุดยอดแต่ละจุดใน${\displaystyle V_{0}}$อยู่ติดกับจุดยอดไม่เกินสองจุดใน${\displaystyle V_{1}}$.
  • ${\displaystyle V_{2}}$เป็นเซตครอบงำสำหรับกราฟย่อยที่เหนี่ยวนำโดย${\displaystyle V_{0}\cup V_{2}}$.

กราฟ${\displaystyle G}$เรียกว่ากราฟโรมันถ้า${\displaystyle \gamma _{R}(G)=2\gamma (G)}$[ ^{2 ] สิ่งนี้เกิด ขึ้น}ก็ต่อเมื่อ${\displaystyle G}$มีฟังก์ชันเด่นแบบโรมันของน้ำหนักขั้นต่ำด้วย${\displaystyle V_{1}=\emptyset }$.

ค่าการครอบงำแบบโรมันของจุดยอดขยายแนวคิดของการครอบงำแบบโรมันโดยพิจารณาว่ามีฟังก์ชันการครอบงำแบบโรมันขั้นต่ำกี่ฟังก์ชันที่กำหนดค่าบวกให้กับจุดยอดนั้น^{[ 3 ]}

สำหรับกราฟ${\displaystyle G}$, อนุญาต${\displaystyle F}$เป็นเซตของทั้งหมด${\displaystyle \gamma _{R}(G)}$-ฟังก์ชัน (ฟังก์ชันครอบงำแบบโรมันที่มีน้ำหนักน้อยที่สุด) สำหรับจุดยอด${\displaystyle v\in V}$ค่านิยม การปกครองของโรมัน${\displaystyle R_{G}(v)}$มีนิยามดังนี้:

${\displaystyle R_{G}(v)=\sum _{f\in F}f(v)}$

คุณสมบัติพื้นฐานบางประการของค่าการครอบงำของโรมันเป็นที่ทราบกันดี: ^{[ 3 ]}

• ${\displaystyle 0\leq R_{G}(v)\leq 2\tau _{R}(G)}$, ที่ไหน${\displaystyle \tau _{R}(G)}$คือจำนวนของ${\displaystyle \gamma _{R}(G)}$-ฟังก์ชัน
• ${\displaystyle \sum _{v\in V(G)}R_{G}(v)=\tau _{R}(G)\gamma _{R}(G)}$
• หากมีการแมปไอโซมอร์ฟิซึมของกราฟไปยังจุดยอด${\displaystyle v}$ใน${\displaystyle G}$ไปยังจุดยอด${\displaystyle v'}$ใน${\displaystyle G'}$, แล้ว${\displaystyle R_{G}(v)=R_{G'}(v')}$

มีการค้นพบผลลัพธ์สุดขั้วหลายประการเกี่ยวกับจำนวนการปกครองของโรมัน

สำหรับการเชื่อมต่อใดๆ${\displaystyle n}$กราฟจุดยอด${\displaystyle G}$กับ${\displaystyle n\geq 3}$,${\displaystyle \gamma _{R}(G)\leq 4n/5}$[ ^{4 ] ความ เท่าเทียม}กันเกิดขึ้นก็ต่อเมื่อ${\displaystyle G}$เป็น${\displaystyle C_{5}}$หรือได้รับจาก${\displaystyle n/5}$สำเนาของ${\displaystyle P_{5}}$โดยการเพิ่มกราฟย่อยที่เชื่อมต่อกันบนเซตของจุดศูนย์กลาง

สำหรับใดๆ${\displaystyle n}$กราฟจุดยอด${\displaystyle G}$กับ${\displaystyle n\geq 3}$,${\displaystyle 5\leq \gamma _{R}(G)+\gamma _{R}({\overline {G}})\leq n+3}$[ ^{4 ]​}

สำหรับใดๆ${\displaystyle n}$กราฟจุดยอด${\displaystyle G}$กับ${\displaystyle n\geq 160}$,${\displaystyle \gamma _{R}(G)\gamma _{R}({\overline {G}})\leq 16n/5}$[ ^{4 ]​}

ถ้า${\displaystyle G}$เป็นการเชื่อมต่อ${\displaystyle n}$กราฟจุดยอดที่มี -${\displaystyle \delta (G)\geq 2}$และ${\displaystyle n\geq 9}$, แล้ว${\displaystyle \gamma _{R}(G)\leq 8n/11}$[ ^{4 ]​}

ปัญหาการตัดสินใจสำหรับการครอบงำแบบโรมันเป็นปัญหา NP-complete แม้ว่าจะจำกัดเฉพาะกราฟแบบสองส่วน กราฟคอ ร์ดัลหรือกราฟระนาบ ก็ตาม ^{[ 1 ]}อย่างไรก็ตาม มีอัลกอริธึมแบบเวลาพหุนามสำหรับการคำนวณจำนวนการครอบงำแบบโรมันบนกราฟช่วงกราฟโคกราฟและกราฟคอร์ดัลที่แข็งแกร่ง^{[ 2 ]}

• ชุดที่โดดเด่น
• การติดป้ายกำกับกราฟ