Graphs that are simultaneously efficient open domination and efficient closed domination graphs

DOI10.1016/J.DAM.2016.09.027MaRDI QIDQ516892zbMATHzbMATHOpenAlexFDO

Authors Sandi Klavžar, Iztok Peterin, Ismael G. Yero

Publication date 15 March 2017

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

computational complexity perfect code efficient open domination efficient closed domination Sierpiński graph

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

Abstract: A graph is an efficient open (resp. closed) domination graph if there exists a subset of vertices whose open (resp. closed) neighborhoods partition its vertex set. Graphs that are efficient open as well as efficient closed (shortly EOCD graphs) are investigated. The structure of EOCD graphs with respect to their efficient open and efficient closed dominating sets is explained. It is shown that the decision problem regarding whether a graph is an EOCD graph is an NP-complete problem. A recursive description that constructs all EOCD trees is given and EOCD graphs are characterized among the Sierpi'nski graphs.

Recommendations

Cites work

Cited in

(13)

This page was built for publication: Graphs that are simultaneously efficient open domination and efficient closed domination graphs

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