Vertex-edge domination in cubic graphs (Q2198396): Difference between revisions

Let \( G = (V, E)\) be a connected graph. A vertex \(u \in V\) is said to \(ve\)-dominate an edge \(xy \in E\) if (1) \(u = x\) or \(u = y\), or (2) \(ux\) or \(uy\) is an edge in \(G\). A set \(D \subseteq V\) is said to be a \(ve\)-dominating set of \(G \) if, for every edge \(e \in E\), there exists a vertex \(u \in D\) such that \(u\) \(ve\)-dominates \(e\). The vertex-edge domination number of \(G\), denoted by \(\gamma_{ve}(G)\), is the minimum cardinality of a vertex-edge dominating set of \(G\), whereas the \(\gamma_{ve}\) ratio \(\rho_{ve}(G)\) is defined as \(\rho_{ve}(G) = \gamma_{ve}(G)/|V|\). The main result of this paper is the following theorem: If \(G\) is a connected cubic graph of order greater than six, then \(\rho_{ve}(G) \leq \frac{10}{31}\), thus affirmatively answering the open question posed by \textit{W. F. Klostermeyer}, \textit{M.-E. Messinger} and \textit{A. Yeo} [``Dominating vertex covers: the vertex-edge domination problem'', Discuss. Math. Graph Theory (to appear)]. On the other hand, the authors present an infinite family of cubic graphs whose \(\gamma_{ve}\) ratio is equal to \(\frac{2}{7}\) and propose the conjecture that asserts that for any cubic graph \(G\) of order \(n > 10\), we have \(\rho_{ve}(G) \leq 2/7\). Finally, they show that the problem of determining the minimum \(\gamma_{ve}\)-dominating set is NP-hard even in cubic planar graphs.