Distance-Dominating Cycles in \(P_3\)-Dominated Graphs

Abstract

Let \(G\) be a connected graph. For \(x,y \in V(G)\) with \(d(x,y) = 2\), we define \(J(x,y) = \{u \in N(x) \cap N(y) | N[u] \cap N[x] \cup N[y]\}\) and \(J'(x,y) = \{u \in N(x) \cap N(y) |\) if \(v \in N(u) \setminus (N[x] \cup N[y])\) then \(N(x) \cup N(y) \cup N(u) \cap N[v]\}\). A graph \(G\) is quasi-claw-free if \(J(x,y) \neq \emptyset\) for each pair \((x,y)\) of vertices at distance \(2\) in \(G\). Broersma and Vumar introduced the class of \(P_3\)-dominated graphs defined as \(J(x,y) \cup J'(x,y) \neq \emptyset\) for each \(x,y \in V(G)\) with \(d(x,y) = 2\). Let \(\kappa(G)\) and \(\alpha_2(G)\) be the connectivity of \(G\) and the maximum number of vertices that are pairwise at distance at least \(2\) in \(G\), respectively. A cycle \(C\) is \(m\)-dominating if \(d(x,C) = \min\{d(x,u) | u \in V(C)\} \leq m\) for all \(x \in V(G)\). In this note, we prove that every \(2\)-connected \(\mathcal{P}_3\)-dominated graph \(G\) has an \(m\)-dominating cycle if \(\alpha_{2m+3}(G) \leq \kappa(G)\).