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 ${\displaystyle G=(V,E)}$ be a graph. A fractional dominating function is a function ${\displaystyle f:V\to [0,1]}$ such that for every vertex ${\displaystyle v\in V}$, the sum of ${\displaystyle f}$ over the closed neighborhood ${\displaystyle N[v]}$ is at least 1:^[1][2]

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

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

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

Properties

For any graph ${\displaystyle G}$, the fractional domination number satisfies:^[1]

${\displaystyle \gamma _{f}(G)\leq \gamma (G)\leq \Gamma (G)\leq \Gamma _{f}(G)}$

where ${\displaystyle \gamma (G)}$ is the domination number, ${\displaystyle \Gamma (G)}$ is the upper domination number, and ${\displaystyle \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.^[2]

For any graph ${\displaystyle G}$ with ${\displaystyle n}$ vertices, minimum degree ${\displaystyle \delta }$, and maximum degree ${\displaystyle \Delta }$:^[2]

${\displaystyle {\frac {n}{\Delta +1}}\leq \gamma _{f}(G)\leq {\frac {n}{\delta +1}}}$

Formulas for specific graph families

For a k-regular graph with ${\displaystyle n}$ vertices and ${\displaystyle k\geq 1}$:^[1][3]

${\displaystyle \gamma _{f}(G)={\frac {n}{k+1}}}$

For the complete bipartite graph ${\displaystyle K_{r,s}}$:^[2]

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

Several graph classes have ${\displaystyle \gamma _{f}(G)=\gamma (G)}$:^[2]

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

For the strong product of graphs ${\displaystyle G\boxtimes H}$:^[2]

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

For the Cartesian product of graphs ${\displaystyle G\square H}$ (Vizing's conjecture, fractional version):^[2]

${\displaystyle \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.^[2]

Variants

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

For ${\displaystyle k}$-regular graphs and specific values of ${\displaystyle k}$, exact formulas exist. For instance, for cycles ${\displaystyle C_{n}}$:^[3]

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

An efficient fractional dominating function satisfies

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

for all vertices ${\displaystyle v}$. Not all graphs admit efficient fractional dominating functions.^[2]

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

The upper fractional domination number ${\displaystyle \Gamma _{f}(G)}$ is the maximum weight among all minimal fractional dominating functions.^[2]

See also

• Dominating set
• Linear programming
• Fractional graph coloring