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.

Definition

Let be a graph. A fractional dominating function is a function such that for every vertex, the sum of over the closed neighborhood is at least 1:
The fractional domination number is the minimum total weight of a fractional dominating function:

Properties

For any graph, the fractional domination number satisfies:
where is the domination number, is the upper domination number, and 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 with vertices, minimum degree, and maximum degree :
For any graph, the fractional edge domination number equals the domination number of the line graph:

Formulas for specific graph families

For a -regular graph with vertices and :
For the complete bipartite graph :
For the cycle graph :
For the path graph :
For the crown graph :
For the wheel graph with vertices:
Several graph classes have :

For the strong product of graphs :
For the Cartesian product of graphs :

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, the sum over its distance- neighborhood is at least one. The corresponding fractional distance k-domination number is denoted.
For -regular graphs and specific values of, exact formulas exist. For instance, for cycles :
An efficient fractional dominating function satisfies
for all vertices. Not all graphs admit efficient fractional dominating functions.
A fractional total dominating function requires that for every vertex, the sum over its open neighborhood is at least one. The fractional total domination number is denoted.
The upper fractional domination number is the maximum weight among all minimal fractional dominating functions.