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

DOI10.1016/J.DAM.2016.09.027zbMATH Open1358.05221arXiv1511.01916OpenAlexW2964079446MaRDI QIDQ516892FDOQ516892

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

Publication date: 15 March 2017

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

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.

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

zbMATH Keywords

computational complexityperfect code[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Sierpi%EF%BF%BD%EF%BF%BDski+graph&go=Go Sierpi��ski graph]efficient open dominationefficient closed domination

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Global strong defensive alliances of Sierpiński-like graphs
• Graphs S(n, k) and a Variant of the Tower of Hanoi Problem
• 1-perfect codes in Sierpiński graphs
• Perfect codes in graphs
• Total Domination in Graphs
• Perfect domination in regular grid graphs
• Construction of trees and graphs with equal domination parameters
• Structural properties of subdivided-line graphs
• Vizing's conjecture: a survey and recent results
• Perfect codes over graphs
• Odd neighborhood transversals on grid graphs
• Open k-monopolies in graphs: complexity and related concepts
• An efficient algorithm to determine all shortest paths in Sierpiński graphs
• Efficient domination in cubic vertex-transitive graphs
• On perfect codes in Cartesian products of graphs
• Perfect codes in direct products of cycles-a complete characterization
• Trees with large total domination number
• Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs
• Tight-optimal circulants vis-à-vis twisted tori
• Efficient dominating sets in circulant graphs with domination number prime
• Error-correcting codes on the Towers of Hanoi graphs
• Shortest paths in Sierpiński graphs
• Efficient open domination in Cayley graphs
• An almost complete description of perfect codes in direct products of cycles
• Perfect codes and independent dominating sets
• Generalized power domination: propagation radius and Sierpiński graphs
• Perfect codes in direct graph bundles
• New results on variants of covering codes in Sierpiński graphs
• Partitioning the vertex set of $G$ to make $G\,\Box\, H$ an efficient open domination graph
• 1-Perfect Codes Over Dual-Cubes vis-à-vis Hamming Codes Over Hypercubes

Cited In (12)

• \([1,k]\)-domination number of lexicographic products of graphs
• On domination game stable graphs and domination game edge-critical graphs
• A survey and classification of Sierpiński-type graphs
• Efficient domination in Cayley graphs of generalized dihedral groups
• Title not available (Why is that?)
• Graphs with unique maximum packing of closed neighborhoods
• On the 2-packing differential of a graph
• (Open) packing number of some graph products
• Domination number of modular product graphs
• On distance and strong metric dimension of the modular product
• Efficient closed domination in digraph products
• Connectivity and some other properties of generalized Sierpiński graphs

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)