On the Monophonic Sets of the Strong Product Graphs

Abstract

For vertices \(u, v\) in a connected graph \(G\), a \(u-v\) chordless path in \(G\) is a \(u-v\) monophonic path. The monophonic interval \(J_G[u, v]\) consists of all vertices lying on some \(u-v\) monophonic path in \(G\). For \(S \subseteq V(G)\), the set \(J_G[S]\) is the union of all sets \(J_G[u, v]\) for \(u, v \in S\). A set \(S \subseteq V(G)\) is a monophonic set of \(G\) if \(J_G[S] = V(G)\). The cardinality of a minimum monophonic set of \(G\) is the monophonic number of \(G\), denoted by \(mn(G)\). In this paper, bounds for the monophonic number of the strong product graphs are obtained, and for several classes, improved bounds and exact values are obtained.