Mitre C. Dourado ; Vitor S. Ponciano ; Rômulo L. O. da Silva - On the monophonic rank of a graph

dmtcs:6835 - Discrete Mathematics & Theoretical Computer Science, September 15, 2022, vol. 24, no 2 - https://doi.org/10.46298/dmtcs.6835
On the monophonic rank of a graphArticle

Authors: Mitre C. Dourado ; Vitor S. Ponciano ; Rômulo L. O. da Silva

    A set of vertices $S$ of a graph $G$ is $monophonically \ convex$ if every induced path joining two vertices of $S$ is contained in $S$. The $monophonic \ convex \ hull$ of $S$, $\langle S \rangle$, is the smallest monophonically convex set containing $S$. A set $S$ is $monophonic \ convexly \ independent$ if $v \not\in \langle S - \{v\} \rangle$ for every $v \in S$. The $monophonic \ rank$ 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.


    Volume: vol. 24, no 2
    Section: Graph Theory
    Published on: September 15, 2022
    Accepted on: August 17, 2022
    Submitted on: October 10, 2020
    Keywords: Computer Science - Discrete Mathematics,Computer Science - Computational Complexity,05C85,G.2.2

    1 Document citing this article

    Consultation statistics

    This page has been seen 1237 times.
    This article's PDF has been downloaded 749 times.