2014/09/04 by Vadim E. Levit, Levit, Vadim E., David Tankus +1
Computer Science · #05C69 (Primary) #05C85 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.1409.1466
openalex publication_date 2014/09/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 minimal 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 WWD(G). We prove that WWD(G) is a subspace of WCW(G), the vector space of weight functions w such that G is w-well-covered. We provide a polynomial characterization of WWD(G) for the case that G does not contain cycles of lengths 4, 5, and 6.