Sulla caratterizzazione dei grafi domistabili
Tóm tắt
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à.
Tài liệu tham khảo
C. Benzaken—P. L. Hammer,Linear separation of dominating sets in graphs sta in «Annals of Discrete Mathematics», n. 3, North-Holland, 1978.
C. Berge,Graphes et Hypergraphes, Dunod, Paris, 1970.
F. Harary,Graph Theory, Addison-Wesley, Reading, Ma., 1969.
V. Chvatal—P. L. Hammer,Aggregation of inequalities in integer programming, sta in «Annals of Discrete Marhematics», n. 1, North-Holland, 1977.