Answers are grounded in this paper and cite their sources.
Let G be a graph with vertex set $V(G)$ and edge set $E(G)$. A set I₀(G) ⊆ V(G) is a vertex independent set if no two vertices in I₀(G) are adjacent in G. We study α₁(G), which is the maximum cardinality of a set I₁(G) ⊆ V(G) that contains exactly one pair of adjacent vertices of G. We call I₁(G) a $1$-nearly vertex independent set of G and α₁(G) a $1$-nearly vertex independence number of G. We provide some cases of explicit formulas for α₁. Furthermore, we prove a tight lower (resp. upper) bound on α₁ for graphs of order n. The extremal graphs that achieve equality on each bound are fully characterised.
No takes yet. Share an insight, caveat, or question.
Zekhaya B. Shozi (2024) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: