Paardominanz in Graphen

In einem Graphen G = (V, E), wenn wir jeden Knoten s als möglichen Standort für einen Wachen betrachten, der in der Lage ist, jeden Knoten in seiner geschlossenen Nachbarschaft Ns zu schützen, dann erfordert "Dominanz", dass jeder Knoten geschützt wird. Somit ist S ⊂ V(G) eine dominierende Menge, wenn ∪s∈SNs = V(G). Für die totale Dominanz muss jeder Wächter wiederum geschützt werden, sodass wir ∪s∈SN(s) = V(G) wünschen. Die (totale) Dominanzzahl γ(G) (γt(G)) ist die minimale Kardinalität über alle minimalen (totale) dominierenden Mengen von G. Wir führen die Paar-Dominanz ein, bei der jeder Wächter einem anderen benachbarten zugewiesen wird und sie als Backup füreinander fungieren. Das heißt, eine paar-dominierende Menge ist eine dominierende Menge, deren induzierter Teilgraph mindestens ein perfektes Matching enthält. Wir zeigen, dass das Paar-Dominanzproblem NP-vollständig ist und präsentieren Schranken für die Paar-Dominanzzahl γp(G). Dieses Papier enthält auch Ergebnisse, die γp(G) mit anderen Dominanzparametern in Beziehung setzen. Zum Beispiel stellen wir fest, dass γ(G) ≤ γt(G) ≤ γp(G) und charakterisieren jene Tripel (a, b, c) positiver Ganzzahlen a ≤ b ≤ c, für die es einen Graphen G gibt, der γ(G) = a, γt(G) = b und γp(G) = c hat. Darüber hinaus führen wir das Konzept der starken Gleichheit von Parametern ein. © 1998 John Wiley & Sons, Inc. Networks 32: 199–206, 1998