An odd dominating set of a simple, undirected graph G = (V,E) is a set of vertices D ⊆ V such that |N[v] ∩ D| ≡ 1 mod 2 for all vertices v ∈ V. It is known that every graph has an odd dominating set. In this paper we consider the concept of connected odd dominating sets. We prove that the problem of deciding if a graph has a connected odd dominating set is NP-complete. We also determine the existence or non-existence of such sets in several classes of graphs. Among other results, we prove there are only 15 grid graphs that have a connected odd dominating set.
Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies
Informacja
SZANOWNI CZYTELNICY!
UPRZEJMIE INFORMUJEMY, ŻE BIBLIOTEKA FUNKCJONUJE W NASTĘPUJĄCYCH GODZINACH:
Wypożyczalnia i Czytelnia Główna: poniedziałek – piątek od 9.00 do 19.00