Fractional dominating set

Short description: Generalization of dominating sets using fractional weights

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 \mathrm{\Gamma }(G)\le {\mathrm{\Gamma }}_f(G)$

where $\gamma (G)$ is the domination number, $\mathrm{\Gamma }(G)$ is the upper domination number, and ${\mathrm{\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 $\mathrm{\Delta }$:

$\frac{n}{\mathrm{\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 ${\mathrm{\Gamma }}_f(G)$ is the maximum weight among all minimal fractional dominating functions.

See also

• Dominating set
• Linear programming
• Fractional graph coloring