ในทฤษฎีกราฟเซตครอบงำแบบเศษส่วน (Fractional dominating set)เป็นการขยายแนวคิดของเซตครอบงำ (Dominating set)ที่อนุญาตให้กำหนดค่าน้ำหนักเศษส่วนระหว่าง 0 ถึง 1 ให้กับจุดยอด แทนที่จะเป็นค่าสมาชิกแบบไบนารี การผ่อนปรนนี้เปลี่ยนปัญหาการครอบงำให้กลายเป็น ปัญหา การเขียนโปรแกรมเชิงเส้นซึ่งมักให้ขอบเขตที่แม่นยำกว่าและช่วยให้สามารถคำนวณได้ในเวลาพหุนาม

อนุญาต${\displaystyle G=(V,E)}$เป็นกราฟฟังก์ชันครอบงำเศษส่วนคือฟังก์ชัน${\displaystyle f:V\to [0,1]}$โดยที่สำหรับทุกจุดยอด${\displaystyle v\in V}$ผลรวมของ${\displaystyle f}$เหนือย่านที่ปิดล้อม${\displaystyle N[v]}$อย่างน้อย 1: ^{[ 1 ] [ 2 ]}

${\displaystyle \sum _{u\in N[v]}f(u)\geq 1}$

จำนวนการครอบงำเศษส่วน${\displaystyle \gamma _{f}(G)}$คือน้ำหนักรวมขั้นต่ำของฟังก์ชันครอบงำเศษส่วน:

${\displaystyle \gamma _{f}(G)=\min \left\{\sum _{v\in V}f(v)\right\}}$

สำหรับกราฟใดๆ${\displaystyle G}$จำนวนการครอบงำเศษส่วนเป็นไปตามเงื่อนไข: ^{[ 1 ]}

${\displaystyle \gamma _{f}(G)\leq \gamma (G)\leq \Gamma (G)\leq \Gamma _{f}(G)}$

ที่ไหน${\displaystyle \gamma (G)}$คือเลขครอบงำ${\displaystyle \Gamma (G)}$คือเลขการครอบงำสูงสุด และ${\displaystyle \Gamma _{f}(G)}$คือจำนวนการครอบงำเศษส่วนบน

จำนวนการครอบงำเศษส่วนสามารถคำนวณได้เป็นคำตอบของโปรแกรมเชิงเส้นโดยใช้ ความเป็นคู่ ที่แข็งแกร่ง^{[ 2 ]}

สำหรับกราฟใดๆ${\displaystyle G}$กับ${\displaystyle n}$จุดยอด, ระดับต่ำสุด${\displaystyle \delta }$และระดับสูงสุด${\displaystyle \Delta }$: ^{[ 2 ]}

${\displaystyle {\frac {n}{\Delta +1}}\leq \gamma _{f}(G)\leq {\frac {n}{\delta +1}}}$

สำหรับกราฟใดๆ${\displaystyle G}$จำนวนการครอบงำ ขอบเศษส่วนเท่ากับจำนวนการครอบงำของกราฟเส้น : ^{[ 3 ]}

${\displaystyle \gamma '_{f}(G)=\gamma (L(G))}$

สำหรับ กราฟ k-ปกติที่มี${\displaystyle n}$จุดยอดและ${\displaystyle k\geq 1}$: ^{[ 1 ] [ 4 ]}

${\displaystyle \gamma _{f}(G)={\frac {n}{k+1}}}$

สำหรับกราฟสองส่วนสมบูรณ์${\displaystyle K_{r,s}}$: ^{[ 2 ]}

${\displaystyle \gamma _{f}(K_{r,s})={\frac {r(s-1)+s(r-1)}{rs-1}}}$

สำหรับกราฟวัฏจักร${\displaystyle C_{n}}$: ^{[ 3 ]}

${\displaystyle \gamma _{f}(C_{n})={\frac {n}{3}}}$

สำหรับกราฟเส้นทาง${\displaystyle P_{n}}$: ^{[ 3 ]}

${\displaystyle \gamma _{f}(P_{n})=\left\lceil {\frac {n}{3}}\right\rceil }$

สำหรับกราฟมงกุฎ${\displaystyle H_{n,n}}$: ^{[ 3 ]}

${\displaystyle \gamma _{f}(H_{n,n})=2}$

สำหรับกราฟวงล้อ${\displaystyle W_{n}}$กับ${\displaystyle n>3}$จุดยอด: ^{[ 3 ]}

${\displaystyle \gamma _{f}(W_{n})=1}$

คลาสกราฟหลายคลาสมี${\displaystyle \gamma _{f}(G)=\gamma (G)}$: ^{[ 2 ]}

• ต้นไม้
• กราฟบล็อก (กราฟที่ทุกบล็อกสมบูรณ์)
• กราฟคอร์ดที่แข็งแกร่ง

สำหรับผลคูณที่แข็งแกร่งของกราฟ${\displaystyle G\boxtimes H}$: ^{[ 2 ]}

${\displaystyle \gamma _{f}(G\boxtimes H)=\gamma _{f}(G)\cdot \gamma _{f}(H)}$

สำหรับผลคูณคาร์ทีเซียนของกราฟ${\displaystyle G\square H}$ (Vizing's conjecture, fractional version):^[2]

${\displaystyle \gamma _{f}(G\square H)\geq \gamma _{f}(G)\cdot \gamma _{f}(H)}$

Since the fractional domination number can be formulated as a linear program, it can be computed in polynomial time, unlike the standard domination number which is NP-hard to compute.^[2]

A fractional distance k-dominating function generalizes the concept by requiring that for every vertex ${\displaystyle v}$, the sum over its distance-${\displaystyle k}$ neighborhood ${\displaystyle N_{k}[v]}$ (vertices at distance at most ${\displaystyle k}$ from ${\displaystyle v}$) is at least one. The corresponding fractional distance k-domination number is denoted ${\displaystyle \gamma _{kf}(G)}$. ^[4]

For ${\displaystyle k}$-regular graphs and specific values of ${\displaystyle k}$, exact formulas exist. For instance, for cycles ${\displaystyle C_{n}}$:^[4]

${\displaystyle \gamma _{kf}(C_{n})={\frac {n}{2k+1}}}$

An efficient fractional dominating function satisfies

${\displaystyle \sum _{u\in N[v]}f(u)=1}$

for all vertices ${\displaystyle v}$. Not all graphs admit efficient fractional dominating functions.^[2]

A fractional total dominating function requires that for every vertex ${\displaystyle v}$, the sum over its open neighborhood ${\displaystyle N(v)}$ (excluding ${\displaystyle v}$ itself) is at least one. The fractional total domination number is denoted ${\displaystyle \gamma _{ft}(G)}$.^[2]

The upper fractional domination number${\displaystyle \Gamma _{f}(G)}$ is the maximum weight among all minimal fractional dominating functions.^[2]

• Dominating set
• Linear programming
• Fractional graph coloring