Fractional dominating set

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 ${\displaystyle 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 ${\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}}}$

For any graph ${\displaystyle G}$, the fractional edge domination number equals the domination number of the line graph:^[3]

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

Formulas for specific graph families

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

${\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}}}$

For the cycle graph ${\displaystyle C_{n}}$:^[3]

${\displaystyle \gamma _{f}(C_{n})={\frac {n}{3}}}$

For the path graph ${\displaystyle P_{n}}$:^[3]

${\displaystyle \gamma _{f}(P_{n})=\left\lceil {\frac {n}{3}}\right\rceil }$

For the crown graph ${\displaystyle H_{n,n}}$:^[3]

${\displaystyle \gamma _{f}(H_{n,n})=2}$

For the wheel graph ${\displaystyle W_{n}}$ with ${\displaystyle n>3}$ vertices:^[3]

${\displaystyle \gamma _{f}(W_{n})=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)}$. ^[4]

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

${\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

References

1. Haynes, Teresa W.; Hedetniemi, Stephen T.; Slater, Peter J. (1998). Fundamentals of Domination in Graphs. Marcel Dekker. pp. 261–262. ISBN 9780429157769.
2. Goddard, Wayne; Henning, Michael A. (2020). "Fractional Dominating Parameters". In Haynes, Teresa W.; Hedetniemi, Stephen T.; Henning, Michael A. (eds.). Topics in Domination in Graphs. Springer. pp. 349–363. doi:10.1007/978-3-030-51117-3_10. ISBN 978-3-030-51117-3.
3. Shanthi, P.; Amutha, S.; Anbazhagan, N.; Bragatheeswara Prabu, S. (2023). "Effects on fractional domination in graphs". Journal of Intelligent & Fuzzy Systems. 44 (5): 7855–7864. doi:10.3233/JIFS-222999.
4. Arumugam, S.; Mathew, Varughese; Karuppasamy, K. (2012). "Fractional distance domination in graphs". Discussiones Mathematicae Graph Theory. 32 (3): 449–459. doi:10.7151/dmgt.1609.