domnum

Domnum is the minimum size of a dominating set in a finite simple graph, a concept in graph theory. A dominating set S is a subset of vertices such that every vertex not in S is adjacent to at least one vertex in S. The domnum of a graph G is often denoted gamma(G) in mathematical literature, while some texts or software use the name domnum to emphasize its role as the domination-number invariant.

Formally, for a graph G = (V,E), domnum(G) = min{|S| : S ⊆ V and every v ∈ V \ S has a neighbor in S}. This invariant captures the smallest number of vertices needed to influence or cover the entire graph through adjacency. It is closely related to other graph parameters such as the independence number and the vertex cover, and it varies with structure and degree distribution.

Basic bounds and examples illustrate its behavior. For a graph with n vertices and maximum degree Δ, domnum(G) ≥ ⌈n/(Δ+1)⌉ and trivially domnum(G) ≤ n. For common graphs: domnum(Kn) = 1; domnum(Pn) = ⌈n/3⌉; domnum(Cn) = ⌊n/3⌋; and domnum(K1,m) = 1. These cases show how topology affects domination needs.

Computational aspects are central to domnum. Determining domnum(G) is NP-hard for general graphs. There are linear-time algorithms for certain classes (such as trees) and approximation methods for general graphs; the greedy algorithm achieves a logarithmic approximation relative to the maximum degree Δ, with an approximation ratio around the harmonic bound H(Δ) ≈ ln Δ + 1.

Applications of domnum appear in network design, facility placement, social networks, and sensor deployments, where a small set of strategically placed nodes must oversee or influence the entire system. See also domination in graphs, minimum dominating set, and related optimization problems.