Fractional dominating set

In graph theory, a fractional dominating set is a generalization of the dominating set concept that allows vertices to be assigned fractional weights between 0 and 1, rather than binary membership. This relaxation transforms the domination problem into a linear programming problem, often yielding more precise bounds and enabling polynomial-time computation.

Let ${\displaystyle G=(V,E)}$ be a graph. A fractional dominating function is a function ${\displaystyle f:V\to [0,1]}$ such that for every vertex ${\displaystyle v\in V}$, the sum of ${\displaystyle f}$ over the closed neighborhood ${\displaystyle N[v]}$ is at least 1:¹²

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

The fractional domination number ${\displaystyle \gamma _{f}(G)}$ is the minimum total weight of a fractional dominating function:

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

For any graph ${\displaystyle G}$, the fractional domination number satisfies:¹

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

where ${\displaystyle \gamma (G)}$ is the domination number, ${\displaystyle \Gamma (G)}$ is the upper domination number, and ${\displaystyle \Gamma _{f}(G)}$ is the upper fractional domination number.

The fractional domination number can be computed as the solution to a linear program by utilizing strong duality.²

For any graph ${\displaystyle G}$ with ${\displaystyle n}$ vertices, minimum degree ${\displaystyle \delta }$, and maximum degree ${\displaystyle \Delta }$:²

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

For any graph ${\displaystyle G}$, the fractional edge domination number equals the domination number of the line graph:³

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

For a k-regular graph with ${\displaystyle n}$ vertices and ${\displaystyle k\geq 1}$:¹⁴

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

For the complete bipartite graph ${\displaystyle K_{r,s}}$:²

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

For the cycle graph ${\displaystyle C_{n}}$:³

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

For the path graph ${\displaystyle P_{n}}$:³

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

For the crown graph ${\displaystyle H_{n,n}}$:³

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

For the wheel graph ${\displaystyle W_{n}}$ with ${\displaystyle n>3}$ vertices:³

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

Several graph classes have ${\displaystyle \gamma _{f}(G)=\gamma (G)}$:²

• Trees
• Block graphs (graphs where every block is complete)
• Strongly chordal graphs

For the strong product of graphs ${\displaystyle G\boxtimes H}$:²

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

For the Cartesian product of graphs ${\displaystyle G\square H}$ (Vizing's conjecture, fractional version):²

${\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.²

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)}$. ⁴

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

${\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.²

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)}$.²

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