Weakly Connected Independence Number of a Graph (European Journal of Pure and Applied Mathematics, 2025)
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 weakly connected set of $G$ if $\langle S\rangle_w$ is connected. $S$ is called a 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 $α_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≥ k+m + 2$, there exists a connected graph $G$ such that $|V(G)| = n$, $α_w(G)= k$ and $α(G)= k +m$.
Keywords: independent, weakly connected set, weakly connected independence number, join, corona, lexicographic