Equivalence dominating sets in graphs

MaRDI QIDQ2860824zbMATH OpenFDO

Authors S. Arumugam, M. Sundarakannan

Publication date 11 November 2013

Published in Utilitas Mathematica (Search for Journal in Brave)

zbMATH Keywords

dominationequivalence dominationequivalence irredundanceequivalence setsirredundance

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Review text

An equivalence set is a subset of vertices of a graph \(G\) with the property that every component of the subgraph induced by it is complete. In this paper, the authors define equivalence dominating and equivalence irredundant sets (equivalence sets that are dominating and irredundant, respectively) as well as several parameters associated to these concepts: the equivalence number and lower equivalence number are the maximum and minimum cardinality of a maximal (with respect to inclusion) equivalence set, the equivalence domination number and upper equivalence domination number are the minimum and maximum cardinality of a minimal equivalence dominating set, and the equivalence irredundance number and upper equivalence irredundance number are the minimum and maximum cardinality of a maximal equivalence irredundant set.NEWLINENEWLINEThese parameters are related to their classical counterparts (independence number, domination number, etc.) and to each other by various inequalities. Moreover, the authors show that the decision problems relating to the equivalence domination number and upper equivalence domination number are NP-complete.

Recommendations

• Equivalence domination in graphs
• Domination equivalence in graphs
• On k-equivalence domination in graphs
• Equi independent equitable dominating sets in graphs
• Equitable domination in graphs
• Graphs with equal domination and covering numbers
• Graphs with equal domination and certified domination numbers
• On graphs having equal domination and codomination numbers
• Degree equitable domination on graphs
• Strong equality of domination parameters in graphs

Cited in

(9)

• A note on the equivalence of a set of egds to a set of FDs
• The parameterized complexity of the equidomination problem
• Domination equivalence in graphs
• Equi independent equitable dominating sets in graphs
• Equivalence domination in graphs
• On k-equivalence domination in graphs
• Equivalence domination number of a tree
• The Domination Equivalence Classes of Paths
• A class of threshold and domishold graphs: Equistable and equidominating graphs

This page was built for publication: Equivalence dominating sets in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2860824)