×

A note on domination parameters of the conjunction of two special graphs. (English) Zbl 1003.05080

A subset \(D\) of the vertex set \(V(G)\) of a graph \(G\) is called a dominating set in \(G\), if each vertex of \(G\) either is in \(D\), or is adjacent to a vertex of \(D\). A dominating set in \(D\) is called a split dominating (or connected dominating) set in \(G\), if the subgraph of \(G\) induced by \(D\) is disconnected (or connected, respectively). The minimum number of vertices of a dominating set, a split dominating set and a connected dominating set in \(G\) are called the domination number \(\gamma(G)\), the split domination number \(\gamma_s(G)\) and the connected domination number \(\gamma_c(G)\) of \(G\). The conjunction \(G\vee H\) of two graphs \(G\), \(H\) is the graph with the vertex set \(V(G)\times V(H)\) in which two vertices \((g_1,h_1)\), \((g_2,h_2)\) are adjacent if and only if \(g_1\), \(g_2\) are adjacent in \(G\) and \(h_1\), \(h_2\) are adjacent in \(H\). The paper studies the mentioned numerical invariants for the conjunctions \(P_n\vee G\), where \(P_n\) is a path of length \(n\).

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI Link