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.

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$.

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)\geq 1$

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

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

Properties

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

$\gamma _{f}(G)\leq \gamma (G)\leq \Gamma (G)\leq \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}}\leq \gamma _{f}(G)\leq {\frac {n}{\delta +1}}$

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

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

Formulas for specific graph families

For a k-regular graph with $n$ vertices and $k\geq 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})=\left\lceil {\frac {n}{3}}\right\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\boxtimes H$:

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

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

$\gamma _{f}(G\square H)\geq \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