Sulla caratterizzazione dei grafi domistabili

Riassunto Viene presentato un algoritmo atto a verificare se un grafo è domistabile, tale essendo ogni grafo in cui qualsiasi insieme dominante minimale di nodi è indipendente. L’algoritmo, che implica un numero di confronti polinomiale, rispetto al numero dei nodi, si basa sulla ricerca di insiemi di nodi dotati di particolari proprietà.

---

Summary In the present paper an algorithm is proposed which verifies ?domistability? in graphs. A graph is called domistable when each minimal dominating set of nodes is also an independent one. The algorithm, polynomial in the number of nodes, is based on the systematic search for node subsets with particular properties.