Es sei ${\displaystyle {}G=(V,E)}$ ein Graph. Die minimale Anzahl von Knoten in einer Knotenüberdeckung von ${\displaystyle {}G}$ heißt Knotenüberdeckungszahl von ${\displaystyle {}G}$.