Nonseparating independent sets and maximum genus of graphs

Vertex degrees (05C07) Paths and cycles (05C38) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Review text

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.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Nonseparating independent sets and maximum genus of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2155662)