Hypo-efficient domination and hypo-unique domination

DOI10.22049/CCO.2016.13553zbMATH Open1365.05224arXiv1601.02234OpenAlexW2963680833MaRDI QIDQ5269926FDOQ5269926

Authors:

Publication date: 28 June 2017

Abstract: For a graph $G$ let $gamma(G)$ be its domination number. We define a graph G to be (i) a hypo-efficient domination graph (or a hypo-$mathcalED$ graph) if $G$ has no efficient dominating set (EDS) but every graph formed by removing a single vertex from $G$ has at least one EDS, and (ii) a hypo-unique domination graph (a hypo-$mathcalUD$ graph) if $G$ has at least two minimum dominating sets,but $G-v$ has a unique minimum dominating set for each $vinV(G)$. We show that each hypo-$mathcalUD$ graph $G$ of order at least $3$ is connected and $gamma(G-v)<gamma(G)$ for all $vinV(G)$. We obtain a tight upper bound on the order of a hypo-$mathcalP$ graph in terms of the domination number and maximum degree of the graph, where $mathcalPinmathcalUD,mathcalED$. Families of circulant graphs which achieve these bounds are presented. We also prove that the bondage number of any hypo-$mathcalUD$ graph is not more than the minimum degree plus one.

Full work available at URL: https://arxiv.org/abs/1601.02234

Recommendations

• Efficient bondage number of a graph
• The bondage numbers and efficient dominations of vertex-transitive graphs
• scientific article; zbMATH DE number 825127
• BOUNDS ON THE DOMINATION NUMBER OF A GRAPH
• scientific article; zbMATH DE number 876673

zbMATH Keywords

domination numberefficient dominationunique dominationhypo-property

Mathematics Subject Classification ID

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

This page was built for publication: Hypo-efficient domination and hypo-unique domination

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