Id: arxiv/2602.16272 Url: https://arxiv.org/abs/2602.16272 Tags: math.CO Score: 0 Title: Nordhaus-Gaddum inequalities for the number of 1-nearly independent vertex subsets Domain: math.CO Source: arxiv Authors: Eric O. D. Andriantiana, Zekhaya B. Shozi Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-02-18 Page: https://delphi.science/r/arxiv/2602.16272 For a graph $G$, a vertex subset is called \emph{$1$-nearly independent} if the subgraph it induces contains exactly one edge. Let $σ_1(G)$ denote the number of such subsets in $G$. In this paper, we study Nordhaus-Gaddum type inequalities for $σ_1$, that is, bounds on the sum $σ_1(G)+σ_1(\overline{G})$, where $\overline{G}$ denotes the complement of $G$. We establish that, for any $n$-vertex graph $G$, we have $σ_1(G)+σ_1(\overline{G})\geq n(n-1)/2,$ with equality if and only if $G$ is either complete or edgeless. We further obtain that among all trees of order $n$, the star $K_{1,n-1}$…