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 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:
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:
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 (Vizing's conjecture, fractional version):
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 , the sum over its distance- neighborhood (vertices at distance at most from ) 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 (excluding itself) 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.