IUMJ

Title: The monophonic number of Cartesian product graphs

Authors: A.P. Santhakumaran and S.V. Ullas Chandran

Issue: Volume 61 (2012), Issue 2, 849-857

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 closed interval $J_G[u,v]$ consists of all the 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 Cartesian product graphs are obtained. Improved bounds and exact values are determined for several classes of Cartesian product graphs. Various realization results are proved.