Fractional dominating set

File:Fractional dominating set.svg

The sum of the weights of each vertex and its neighbors (its closed neighborhood) is at least 1. The assignment of weights is therefore a fractional dominating set. One may consider the sum of all weights of the graph across all fractional dominating sets; the smallest of these is the graph's fractional domination number. The graph shown has an optimal set shown, with a total sum of $7/3$.

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.

Definition

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

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

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

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

Properties

For any graph $G$, the fractional domination number satisfies:

${\gamma }_f(G)\le \gamma (G)\le \Gamma (G)\le {\Gamma }_f(G)$

where $\gamma (G)$ is the domination number, $\Gamma (G)$ is the upper domination number, and ${\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 $G$ with $n$ vertices, minimum degree $\delta$, and maximum degree $\Delta$:

$\frac{n}{\Delta +1}\le {\gamma }_f(G)\le \frac{n}{\delta +1}$

For any graph $G$, the fractional edge domination number equals the domination number of the line graph:

$\gamma {\text{'}}_f(G)=\gamma (L(G))$

Formulas for specific graph families

For a k-regular graph with $n$ vertices and $k\ge 1$:

${\gamma }_f(G)=\frac{n}{k+1}$

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

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

For the cycle graph $C_n$:

${\gamma }_f(C_n)=\frac{n}{3}$

For the path graph $P_n$:

${\gamma }_f(P_n)=\lceil \frac{n}{3}\rceil$

For the crown graph $H_{n,n}$:

${\gamma }_f(H_{n,n})=2$

For the wheel graph $W_n$ with $n>3$ vertices:

${\gamma }_f(W_n)=1$

Several graph classes have ${\gamma }_f(G)=\gamma (G)$:

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

For the strong product of graphs $G⊠H$:

${\gamma }_f(G⊠H)={\gamma }_f(G)\cdot {\gamma }_f(H)$

For the Cartesian product of graphs $G◻H$ (Vizing's conjecture, fractional version):

${\gamma }_f(G◻H)\ge {\gamma }_f(G)\cdot {\gamma }_f(H)$

Computational complexity

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.

Variants

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

For $k$-regular graphs and specific values of $k$, exact formulas exist. For instance, for cycles $C_n$:

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

An efficient fractional dominating function satisfies

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

for all vertices $v$. Not all graphs admit efficient fractional dominating functions.

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

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

See also

• Dominating set
• Linear programming
• Fractional graph coloring