Nonseparating independent sets and maximum genus of graphs (Q2155662)

A subset $I$ of vertices of a graph $G$ is called a non-separating independent set if no two vertices of $I$ are adjacent and $G-I$ is connected. The maximum size of a non-separating independent set of $G$ is denoted by $Z(G)$ and is called the maximum non-separating independence number. For a connected graph $G$ and a surface $P$, the graph $G$ can be embedded into $P$ if there exists a polyhedron $\Sigma$ on $P$ such that the $1$-skeleton (the set of edges and vertices of the surface $P$) of $\Sigma$ has a subgraph homeomorphic to $G$. The components of $\Sigma-G$ are called the faces of the embedding. When each face is homeomorphic to an open disc, the embedding is called a $2$-cellular. The maximum genus of a connected graph $G$, denoted by $\gamma_M(G)$, is the largest genus of an orientable surface on which $G$ admits a cellular embedding. Let $n$ and $l$ be two positive integers with $n\geq 2l$. For any two numbers $i$, $j$ where $1\leq i$, $j\leq n$, define function \[ d(i,j)=\left\{ \begin{array}{lr} {|i-j|},& \mbox{ if }|i-j|\leq \frac{n}{2},\\n-|i-j|,& \mbox{otherwise.} \end{array} \right. \] As a matter of convenience, set $v_i=i$, $1\leq i\leq n$. A circular graph $G=C(n,l)$ of order $n$ is one spanned by a cycle $C_n=1-2-\cdots -n-1$ together with the chords $(i,j)\in E(G)$ if and only if $d(i,j)=l$ $(l>1)$. The authors firstly give an upper bound for $Z(G)$ of regular graphs and determine $Z(G)$ for some types of circular graphs. Secondly, they have shown a relationship between $Z(G)$ and the maximum genus $\gamma_M(G)$ of a general graph.