Unterzeichnete doppelte römische Dominanz auf kubischen Graphen

Das Problem der signierten doppelten römischen Dominanz ist ein kombinatorisches Optimierungsproblem auf einem Graphen, bei dem jeder Ecke ein Label von ±1, 2, 3 zugewiesen werden soll, sodass die Gesamtsumme der zugewiesenen Labels minimiert wird. Hier ist die Durchführbarkeit gegeben, wenn (i) Ecken mit den Labels ±1 mindestens einen Nachbarn mit dem Label 2 oder 3 haben; (ii) jede Ecke mit dem Label −1 hat einen Nachbarn mit dem Label 3 oder mindestens zwei Nachbarn mit dem Label 2; und (iii) die Summe der Labels über die geschlossene Nachbarschaft jeder Ecke positiv ist. Das kumulierte Gewicht einer optimalen Kennzeichnung wird als signierte doppelte römische Dominanznummer (SDRDN) bezeichnet. In dieser Arbeit betrachten wir zunächst das Problem auf allgemeinen kubischen Graphen der Ordnung n, für die wir mittels der Entlade-Methode eine scharfe Untergrenze von n/2+Θ(1) für die SDRDN präsentieren. Darüber hinaus leiten wir eine neue beste obere Grenze ab. Da wir oft in der Lage sind, die SDRDN über die Klasse der kubischen Graphen einer festen Ordnung zu minimieren, untersuchen wir in diesem Kontext verallgemeinerte Petersen-Graphen aus unabhängigem Interesse, für die wir einen proof mit geführter Einschränkung vorschlagen. Diese Erkenntnisse nutzen wir dann, um die SDRDNs von subkubischen 2×m-Gittergraphen zu bestimmen, unter anderem Ergebnisse.