Domination Number Calculator

min dominating set γ(G)

CalculatorsFreeNo Signup
4.3(324 reviews)
All Tools

Loading tool...

About Domination Number Calculator

A domination number calculator computing γ(G): minimum dominating set. Every vertex is dominated (in S or has neighbor in S). γ(G) ≤ n/2 for connected graphs with n≥2. γ(K_n)=1, γ(C_n)=⌈n/3⌉, γ(P_n)=⌈n/3⌉. Client-side.

Domination Number Calculator Features

  • γ(G) value
  • Ore's bound
  • Common graphs
  • Total domination
  • Independent domination
Domination number γ(G): minimum dominating set S where N[S]=V (every vertex in S or adjacent to S). γ(K_n)=1, γ(C_n)=γ(P_n)=⌈n/3⌉. Ore (1962): γ(G)≤n/2 for connected graphs, n≥2. NP-hard in general.

How to Use

Select graph:

  • γ: Domination number
  • Set: Dominating set
  • Ore: γ ≤ n/2

Domination Variants

Total domination γ_t: every vertex has a neighbor in S (even vertices in S). Independent domination i(G): dominating set that is also independent. Connected domination γ_c: S induces a connected subgraph. Each has different complexity.

Applications

Facility location: place servers to cover all clients. Wireless networks: place access points. Social networks: select influencers to reach everyone. Monitoring: place sensors to observe all locations.

Step-by-Step Instructions

  1. 1Select graph.
  2. 2Compute γ(G).
  3. 3Find dominating set.
  4. 4Check Ore bound.
  5. 5Try variants.

Domination Number Calculator — Frequently Asked Questions

How is γ related to other invariants?+

γ ≤ α (any maximal independent set dominates). γ ≤ τ (any vertex cover dominates). γ ≤ n - Δ (remove a max-degree vertex's non-neighbors). These bounds often give useful estimates.

Is this NP-hard?+

Yes, SET COVER reduces to DOMINATING SET. NP-hard even for planar graphs. But polynomial for: trees (greedy), interval graphs, cographs, and graphs of bounded treewidth. Parameterized complexity: W[2]-complete.

What's Ore's bound?+

γ(G) ≤ n/2 for connected graphs with n≥2 (Ore, 1962). Sharper: γ(G) ≤ n(1+ln(δ+1))/(δ+1) using greedy. For cubic graphs: γ ≤ n/3 (Reed, 1996). These bounds guide algorithm design.

More Calculators Tools

Explore all 639 other calculators tools available on Generatr

1-Sample Z-Test Calculator2-Sample Z-Test Calculator3D Surface Area CalculatorA/B Testing Significance CalculatorAbsolute Value CalculatorAbundant Number CheckerAccelerated Aging CalculatorAchromatic Number CalculatorAcyclic Chromatic Number CalculatorAdditive Persistence CalculatorAge CalculatorAging Test CalculatorAlbertson Index CalculatorAlgebraic Connectivity CalculatorAliquot Sequence CalculatorAliquot Sum CalculatorAlternating Series Test CalculatorAmicable Number FinderAnnuity CalculatorAPY CalculatorAquarium CO2 Drop CheckerArea CalculatorArea Under Curve CalculatorArithmetic Sequence CalculatorArmstrong Number CalculatorASCVD Risk CalculatorAspect Ratio CalculatorAtom Bond Connectivity CalculatorAugmented Eccentric Connectivity CalculatorAugmented Zagreb Index Calculator
View all 639 calculators tools
Share this tool: