Orientable domination in product-like graphs (Q2109114): Difference between revisions

Given an undirected graph \(G\), the orientable domination number of \(G\) is \[ DOM(G) = \max\{\gamma(D) : D\text{ is an orientation of }G\}. \] In this paper, the authors investigate the orientable domination number on different product graphs such as corona, Cartesian, and lexicographic products. Also, they determine the values of \(DOM(K_{n_1,n_2,n_3})\) for arbitrary positive integers \(n_1\), \(n_2\) and \(n_3\). Let \(G\) and \(H\) be two graphs. The corona, \(G\odot H\), of \(G\) and \(H\) is the graph obtained from the disjoint union of \(G\) and \(n(G)\) copies of \(H\), which we denote by \(H_u\) for every \(u \in V(G)\), and then joining each \(u\in V(G)\) to all vertices of \(H_u\). The join of \(G\) and \(H\) is the graph \(G + H\) obtained from the disjoint union of \(G\) and \(H\) by connecting each vertex of \(G\) with each vertex of \(H\). It is observed that \(DOM(G + K_1)\in\{DOM(G), DOM(G) + 1\}\). The Cartesian product \(G\Box H\) of two graphs \(G\) and \(H\) is the graph with vertex set \(V(G)\times V(H)\) and two vertices \((u,v) \) and \( (x,y)\) are adjacent if either \(u=x\) and \(vy\in E(H)\) or \(ux\in E(G)\) and \(v=y\). The lexicographic product \(G \circ H\) of \(G\) and \(H\) is the graph with \(V(G\circ H) = V(G) \times V(H)\) and two vertices \((x, y)\) and \((u, v)\) are adjacent in \(G \circ H\) if either \(xu \in E(G)\), or \(x = u\) and \(yv \in E(H)\). The main results of this paper are: \begin{itemize} \item[1.] If \(G\) and \(H\) are two graphs, then \[ DOM(G \odot H) =\left\{\begin{array}{lll} DOM(H)n(G) & \text{ if } DOM(H + K_1) = DOM(H), \\ DOM(H)n(G) + DOM(G) & \text{ if } DOM(H + K_1) = DOM(H)+1. \end{array}\right. \] \item[2.] For any graphs \(G\) and \(H\), \[ \max\{DOM(G)\alpha(H), \alpha(G)DOM(H)\}\le DOM(G \Box H)\le \min\{DOM(G)n(H), n(G)DOM(H)\}. \] \item[3.] If \(1 \le n_1 \le n_2 \le n_3\), then \[ DOM(K_{n_1,n_2,n_3} ) =\left\{\begin{array}{lll} n_3 & \text{ if } n_3\ge 3 \\ 3 & \text{ if } n_1=n_2=n_3=2 \\ 2 & \text{ otherwise}. \end{array}\right. \] This extends a result of \textit{G. Chartrand} et al. [Congr. Numerantium 119, 51--63 (1996; Zbl 0899.05028)]. \end{itemize}