On the monophonic rank of a graph

Abstract

A set of vertices $S$ of a graph $G$ is $monophonicallyconvex$ if every induced path joining two vertices of $S$ is contained in $S$. The $monophonicconvexhull$ of $S$, $⟨S⟩$, is the smallest monophonically convex set containing $S$. A set $S$ is $monophonicconvexlyindependent$ if $v\notin ⟨S-\{v\}⟩$ for every $v\in S$. The $monophonicrank$ of $G$ is the size of the largest monophonic convexly independent set of $G$. We present a characterization of the monophonic convexly independent sets. Using this result, we show how to determine the monophonic rank of graph classes like bipartite, cactus, triangle-free and line graphs in polynomial time. Furthermore, we show that this parameter can be computed in polynomial time for $1$-starlike graphs, $i.e.$, for split graphs, and that its determination is $NP$-complete for $k$-starlike graphs for any fixed $k\ge 2$, a subclass of chordal graphs. We also consider this problem on the graphs whose intersection graph of the maximal prime subgraphs is a tree.

14 pages, 2 figures