The upper connected outer connected monophonic number of a graph

Abstract

For a connected graph $G$ of order at least two, a connected outer connected monophonic set $S$ of $G$ is called a minimal connected outer connected monophonic set if no proper subset of $S$ is a connected outer connected monophonic set of $G$. The upper connected outer connected monophonic number $c{m}_{co}^{+}(G)$ of $G$ is the maximum cardinality of a minimal connected outer connected monophonic set of $G$. We determine bounds for it and find the upper connected outer connected monophonic number of certain classes of graphs. It is shown that for any two integers $a,b$ with $4\le a\le b\le p-2$, there is a connected graph $G$ of order $p$ with $c{m}_{co}(G)=a$ and $c{m}_{co}^{+}(G)=b$. Also, for any three integers $a,b$ and $n$ with $4\le a\le n\le b$, there is a connected graph $G$ with $c{m}_{co}(G)=a$ and $c{m}_{co}^{+}(G)=b$ and a minimal connected outer connected monophonic set of cardinality $n$, where $c{m}_{co}(G)$ is the connected outer connected monophonic number of a graph.

KEYWORDS:

• Monophonic set
• outer connected monophonic set
• connected outer connected monophonic set
• minimal connected outer connected monophonic set
• upper connected outer connected monophonic number

Subject classification codes::

• 05C12

Disclosure statement

No potential conflict of interest was reported by the author(s).