Weitere Ergebnisse zur k-römischen Dominanz in Graphen

Zusammenfassung Im Jahr 2016 definierten Beeler et al. die doppelte römische Dominanz als eine Variation der römischen Dominanz. Etwas später, im Jahr 2021, führten Ahangar et al. das Konzept der k -römischen Dominanz in Graphen ein und beschlossen einige Ergebnisse zum Fall der dreifachen römischen Dominanz. Im Jahr 2022 untersuchten Amjadi et al. die quadruple Version dieses römischen Dominanzproblems. Gegeben eine Beschriftung der Knoten eines Graphen steht AN(v) für die Menge der Nachbarn eines Knotens v mit einer positiven Beschriftung. In diesem Papier setzen wir die Untersuchung der k -römischen Dominanzfunktionen (k -RDF) in Graphen fort, die mit den vorherigen Versionen übereinstimmt, wenn 2 k 4 2 ≤ k ≤ 4. Nämlich, f ist eine k -RDF, wenn f(Nv) k+|AN(v)| f(Nv) ≥ k + |AN(v)| für alle v. Wir beweisen, dass das zugehörige Entscheidungsproblem NP-vollständig ist, selbst wenn es auf sternkonvexe und combkonvexe bipartite Graphen beschränkt ist, und wir geben auch scharfe Schranken und genaue Werte für mehrere Klassen von Graphen an.