Description
Az irányítatlan gráfok esetén domináló halmaznak nevezzük a csúcsok egy részhalmazát, ha minden rajtuk kívüli csúcsnak létezik szomszédja a domináló halmazból. Totálisan dominálónak pedig pontosan akkor, ha a gráf bármely csúcsára igaz ez, azaz ha a szomszédságok uniója lefedi a csúcshalmazt. A minimális méretű domináló/totálisan domináló halmaz méretét a gráf dominálási/totális dominálási számának nevezzük.
Irányított gráfok esetén a két fogalom analóg módon általánosítható, de egy csúcs csak azokat a csúcsokat "dominálja", amikbe vezet belőle él. Az irányított értelemben vett dominálási/totális dominálási szám is analógan definiálható.
Ha adott egy G irányítatlan gráf, akkor a (felső) megirányítható totális dominálási száma (upper orientable total domination number) az a szám, ami a maximuma azoknak az irányított értelemben vett totális dominálási számoknak, ahol az irányított gráfot úgy kapjuk, hogy vesszük az irányítatlan gráf összes lehetséges megirányítását.
Szeretnék az ÚNKP témavezetettemmel közös kutatásról mesélni, amiben azt az esetet vizsgáljuk, amikor ez a megirányítható totális dominálási szám közel van a gráf csúcsszámához.