Domination equivalence in graphs

MaRDI QIDQ2369388zbMATH OpenFDO

Authors Jean R. S. Blair, Sandra M. Hedetniemi, Stephen T. Hedetniemi, S. Horton, Wayne Goddard

Publication date 9 May 2006

Published in AKCE International Journal of Graphs and Combinatorics (Search for Journal in Brave)

zbMATH Keywords

open domination-equivalent pair

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph theory (05C99)

Review text

A DE-pair (domination-equivalent pair) consists of two disjoint subsets of vertices with the same closed neighborhood. Likewise, an ODE-pair (open domination-equivalent pair) consists of two disjoint subsets of vertices with the same open neighborhood. One may think of an ODE-pair as a partial coloring of the vertices with red and blue, such that every vertex that has a red neighbor also has a blue neighbor, and vice versa. There is a similar interpretation for DE-pairs. The paper considers the question of determining the smallest and largest subsets over all such pairs. It provides sharp bounds on these for general graphs and for trees, and shows that the associated parameters are computable for trees but intractable in general.

Recommendations

• Equivalence domination in graphs
• Equivalence dominating sets in graphs
• Equivalence domination number of a tree
• On equality in an upper bound for the equivalence domination number
• The Domination Equivalence Classes of Paths

Cited in

(2)

• Equivalence dominating sets in graphs
• The Domination Equivalence Classes of Paths

This page was built for publication: Domination equivalence in graphs

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