×

Perfect secure domination in graphs. (English) Zbl 1374.05174

Let \(G\) be a graph and let \(S\subseteq V(G)\). Set \(S\) is a dominating set of \(G\) if every vertex outside of \(S\) has a neighbor in \(S\). A dominating set \(S\) is called secure dominating set if for every vertex \(x\) outside of \(S\) there exists his neighbor \(y\in S\), such that if we exchange \(x\) by \(y\) in \(S\), the new set remains a dominating set. Furthermore a secure dominating set is called perfect secure dominating set if a vertex \(y\) is unique for every vertex \(x\).
The authors investigate perfect secure dominating sets of minimum cardinality called the perfect secure dominating number of a graph. This number is derived for several classical families of graphs as complete graphs, complete bipartite graphs, paths, cycles and some others as well as for some operations as Cartesian product of graphs and join of two graphs.

MSC:

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