On the complement connected Steiner number of a graph

Abstract

For a connected graph $G=(V,E)$ of order $p \geq 3$, a Steiner set $W \subseteq V(G)$  is said to be a complement connected Steiner set if $W=V(G)$ or the subgraph $\langle V(G)-W \rangle$ is connected.  The minimum cardinality of a complement connected Steiner set of $G$ is the complement connected Steiner number of $G$ and is denoted by $s _{cc}(G)$.  It is shown that for every triplet $a, b, c$ of integers with $3 \leq a \leq b \leq c$, there exists a connected graph $G$ with $m_{cc}(G)=a, g_{cc}(G)=b$, and $s_{cc}(G)=c$,  where $m_{cc}(G)$ and $g_{cc}(G)$ are the complement connected monophonic number  and the complement connected geodetic number of the graph $G$, respectively. It is proved that for any two integers $a$ and $b$ with $3 \leq a \leq b$, there exists a connected graph $G$ such that $m_{cc}(G)=s_{cc}(G)=a$ and $g_{cc}(G)=b$.   Also, we have shown that, for every triplet $a, b, c$ of  integers with $3 < a < b < c$ and $b>a+1$,  there exists a connected graph $G$ with $m_{cc}(G)=a, s_{cc}(G)=b$, and $g_{cc}(G)=c$.