Well-dominated graphs without cycles of lengths [formula omitted] and [formula omitted].

Let G be a graph. A set S of vertices in G dominates the graph if every vertex of G is either in S or a neighbor of a vertex in S . Finding a minimum cardinality set which dominates the graph is an NP -complete problem. The graph G is well-dominated if all its minimal dominating sets are of the same cardinality. The complexity status of recognizing well-dominated graphs is not known. We show that recognizing well-dominated graphs can be done polynomially for graphs without cycles of lengths 4 and 5 , by proving that a graph belonging to this family is well-dominated if and only if it is well-covered. Assume that a weight function w is defined on the vertices of G . Then G is w -well-dominated if all its minimal dominating sets are of the same weight. We prove that the set of weight functions w such that G is w -well-dominated is a vector space, and denote that vector space by W W D ( G ) . We show that W W D ( G ) is a subspace of W C W ( G ) , the vector space of weight functions w such that G is w -well-covered. We provide a polynomial characterization of W W D ( G ) for the case that G does not contain cycles of lengths 4 , 5 , and 6 . [ABSTRACT FROM AUTHOR]