Weakly Connected Independence Number of a Graph

Abstract

Let $G$ be a simple undirected connected graph with vertex and edge sets $V(G)$ and $E(G)$, respectively. The subgraph $\langle S\rangle_w$ of $S \subseteq V(G)$ is the graph whose vertex set is $N[S]$ and whose edge set $E_w$ consists of edges in $E(G)$ incident to some vertex in $S$. A subset $S$ of $V(G)$ is a \emph{weakly connected set} of $G$ if $\langle S\rangle_w$ is connected. $S$ is called a \emph{weakly connected independent set} (WCIS) of $G$ if it is both weakly connected and independent. In this paper, we characterize the weakly connected independent sets in the join, corona, and the lexicographic product of two graphs. From these characterizations the weakly connected independence numbers of the corresponding graphs are easily determined. Also, characterization of graphs $G$ with weakly connected independence numbers $\alpha_w(G)$ equal to 1, $n-1$ and $n$ are given. It is also shown that for any  non-negative integers $k$,  $m$, and $n$ with $k > m + 1$ and $n\geq k+m + 2$, there exists a connected graph $G$ such that $|V(G)| = n$, $\alpha_w(G)= k$ and $\alpha(G)= k +m$.